рекурсия и итерация

Оно?

У тебя не сама итерация выделяет память, а код внутри нее. В случае итерации шаги итерации независимы - можно их совершать один за другим и отбрасывать все, что было на предыдущих.В случае рекурсии так не получается. Не всегда по крайней мере.

а что же она должна вычислять-то?

Понятное дело, что в конечном итоге все сводится к числам, но смысл того, что мы вычисляем, может быть чем угодно, например графом.

У тебя не сама итерация выделяет память, а код внутри нее.

охлол. Этот код и есть итерация, если что.

Вот этот код, тогда тоже итерация? :

Number ack(m, n)
{
   vector<Number> s;
   while(m!=0 || s.length()>0) {
      if(n==0) m--;
      else {
         s.append(m);
         n = n--;
      }
      if(m==0 && s.length() > 0) {
         m=s.pop();
         m--;
         n = n++;
      }
   }
   return n+1;
}

Ага, только людям нравится участвовать в специальной олимпиаде.

действие(изменение окружения) не есть число.

а есть ещё что-то? Что-то кроме комбинации чисел? Может есть любовь, радость? Ты рассказывай, а то я же не в курсе.

не является итерацией?

это итерация к которой ты прилепил выделение памяти. Но оно тут не нужно, ибо очевидно, что алгоритму нужно seq.length() памяти, и внутри цикла это предопределённая константа. Т.е. выделение памяти является инвариантным для тела цикла.

В рекурсивном алгоритме невозможно указать, какое именно количество памяти будет использовано(точно).

Да, факториал выше не является истинной рекурсией. Но он являлся-бы, если-бы мне было нужно хранить не все числа, а только некоторые. Или все, но НУЖНО.

Он просто накапливает результат. Каждая итерация не зависит от следующих итераций. В рекурсивном же процессе у тебя будет «стек» промежуточных значений. И именно из них будет состоять память, про которую тебе тут говорят.

Понятное дело, что в конечном итоге все сводится к числам, но смысл того, что мы вычисляем, может быть чем угодно, например графом.

ну и где я говорил, что «не может быть графом, а только целое число от 3 до 7»?

Этот код и есть итерация, если что.

да, но это только от твоей криворукости. Намного быстрее сразу выделить кусок памяти, чем добавлять по 1 символу.

Это рекурсивный процесс.

Намного быстрее сразу выделить кусок памяти, чем добавлять по 1 символу.

Тогда можно и в обходе бинарного дерева сразу выделить кусок памяти размером log_2(N).

Тогда обход дерева станет итеративным?

n = n--;

Завязывай с тяжелыми наркотиками.

Прочти уже SICP.

(define (factorial n)
   (if (= n 1)
       1
       (* n (factorial (- n 1)))))

vs

(define (factorial n)
   (fact-iter 1 1 n))

 (define (fact-iter product counter max-count)
   (if (> counter max-count)
       product
       (fact-iter (* counter product)
                  (+ counter 1)
                  max-count)))

Или же

(define (fib n)
   (cond ((= n 0) 0)
         ((= n 1) 1)
         (else (+ (fib (- n 1))
                  (fib (- n 2))))))

vs

(define (fib n)
   (fib-iter 1 0 n))

 (define (fib-iter a b count)
   (if (= count 0)
       b
       (fib-iter (+ a b) a (- count 1))))

Неужели непонятна разница? Развели тут...

Это рекурсивный процесс.

В чём тогда отличие рекурсия и итерация (комментарий) от рекурсия и итерация (комментарий) ?

В обоих случаях есть главный цикл. В обоих случаях внутри цикла происходит работа с памятью. В обоих случаях можно заранее вычислить максимальный размер необходимого куска памяти.

Все уже говорилось. Читай SICP, может дойдет.

В том, что у тебя нет стека для промежуточных результатов. Может такое бытовое описание тебя устроит?

Тогда можно и в обходе бинарного дерева сразу выделить кусок памяти размером log_2(N).

да, только не log2(N), а некое log2(N)<= h <= N.

Тогда обход дерева станет итеративным?

безусловно. Вот только нужно выделить либо N памяти, а это вполне может быть и 100Гб, либо обходить всё дерево перед каждым шагом, что-бы узнать текущее значение h. Естественно это можно, и не сложно, вот только работать оно будет медленнее простого списка, а памяти жрать будет больше.

Потому на практике такую итеративную замену никто не использует. А используют машинный стек + машинозависимые костыли для ограничения h + рекурсивный алгоритм обхода на аппаратном стеке.

Неужели непонятна разница? Развели тут...

ну ты правильно на SICP сослался, там есть хорошие и наглядные картинки как раз на эту тему. И объяснение вполне понятное. И ещё и по-русски. Что сразу на ЛОР тащить своё неосиляторство?

В том, что у тебя нет стека для промежуточных результатов.

Почему res в

vector<Number> res;
for(i=0; i < seq.length(); i++)
{
   if(seq[i] > 10) res.append(seq[i);
}

vector<Number> s;
while(m!=0 || s.length()>0) {
   if(n==0) m--;
   else {
      s.append(m);
      n = n--;
   }
   if(m==0 && s.length() > 0) {
      m=s.pop();
      m--;
      n = n++;
   }
}

считаешь?

В обоих случаях есть главный цикл. В обоих случаях внутри цикла происходит работа с памятью. В обоих случаях можно заранее вычислить максимальный размер необходимого куска памяти.

вопрос «можно/неможно» никого не волнует. В рекурсивном алгоритме память никто заранее не выделяет, она сама выделяется. В итеративном она выделяется один раз. Естественно, любой итеративный алгоритм ты при желании можешь переписать как рекурсивный, выделяя память в любых количествах. Т.к. рекурсия — более общий случай. Обратное неверно, т.к. обход дерева или скажем qsort невозможно переписать в итеративный вид без велосипедной эмуляции стека возвратов для хранения контекстов.

Потому на практике такую итеративную замену никто не использует. А используют машинный стек...

В компиляторе Scheme стек совсем не машинный.

Вот только нужно выделить либо N памяти, а это вполне может быть и 100Гб,

Если аналог стека требует 100Гб, то машинный стек гарантировано упадёт с stack overflow.

А аналог я и на файл могу отобразить при очень большом «стеке».

Потому, что в первом случае ты решаешь задачу построения последовательности на основе фильтрации существующей. В твоем решении нет никаких промежуточных результатов, который ты хранишь в «стеке». Я думаю, что ты без труда напишешь аналогичный рекурсивную версию, которая будет это делать.

В рекурсивном алгоритме память никто заранее не выделяет, она сама выделяется. В итеративном она выделяется один раз.

То есть

vector<Number> res;
for(i=0; i < seq.length(); i++)
{
   if(seq[i] > 10) res.append(seq[i);
}

по твоим понятиям рекурсивный. Память ведь больше одного раза выделяется.

Потому на практике такую итеративную замену никто не использует. А используют машинный стек...

В компиляторе Scheme стек совсем не машинный.

а разве где-то в продакшене используются примитивные структуры вроде бинарного дерева написанные на схеме? Или велосипедный qsort на схеме?

Если аналог стека требует 100Гб, то машинный стек гарантировано упадёт с stack overflow.

нет. Потому-что машинный стек не нужно _заранее_ выделять.

А аналог я и на файл могу отобразить при очень большом «стеке».

мне жаль твоих пользователей, которые плачут, когда твой 100Гб стек отображаются на их 64Гбый SSD. Особенно это печально, если из 100Гб нужно все 200 байт. Но ты же не думаешь, а «отображаешь»...

В твоем решении нет никаких промежуточных результатов, который ты хранишь в «стеке».

Что понимать под промежуточными результатами? Ну ладно...

vector<Number> res, s;
for(i=0; i < seq.length(); i++)
{
   if(seq[i] > 10) {
      if(!found_sorted(s), seq[i])
        res.append(seq[i);
      insert_sorted(s, seq[i]);
   }
}

s определённо промежуточная и динамически выделяемая. Это делает эту функцию рекурсивной?

Потому-что машинный стек не нужно _заранее_ выделять.

Не понял. Это спасёт при выполнении

int rec_sum(list s)
{
   if(s.next == NULL) return s.data;
   return s.data + rec_sum(s.next, i+1);
}

да, но это только от твоей криворукости. Намного быстрее сразу выделить кусок памяти, чем добавлять по 1 символу.

А по-моему, от твоего тугоумия. Не я-то код писал.

Ну и не важно, какой там код, хороший или плохой.

по твоим понятиям рекурсивный. Память ведь больше одного раза выделяется.

по моим понятиям это кривая итерация, записанная как рекурсия. В силу того, что рекурсия более проста и более понятна, такой вариант очень хорош, если конечно объём памяти и скорость не имеют значения.

Потому-что ИМХО если скорость/память не имеет значения, то самое важное — обеспечить максимально понятный код. Т.е. если алгоритм рекурсивный (от математиков), то его и надо записывать в виде рекурсии, как (define (factorial n)(if (= n 0) 1 (* n (factorial (- n 1))))), а не как-то иначе. потому-что преждевременная оптимизация == зло.

А если скорость/память значение имеет, то это совсем иная история.

а разве где-то в продакшене используются примитивные структуры вроде бинарного дерева написанные на схеме?

Пишут, что здесь: http://www.getkahu.com/

Реализация Scheme под названием Racket

Это делает эту функцию рекурсивной?

У тебя тут нет функции. А процесс рекурсивным будет тогда, когда ты будешь использовать «раскручивать» ранее накопленные промежуточные результаты. Посмотри на схемки рекурсивных и итеративных процессов в SICP'е.

А на википедии написано: факториал — произведение всех натуральных чисел от 1 до n включительно.

Так что надо

(define (factorial n)
  (for/fold ([res 1]) ([i (in-range 1 n)])
    (* res i)))

О по-моему, от твоего тугоумия. Не я-то код писал.

при чём тут я? Тугодумие у тебя, если ты берёшь как пример чужой код, который не понимаешь. Но для тех, кто в танке, поясню: да, это НЕ итеративный алгоритм, ибо тут нет единого куска памяти, в котором ты работаешь. На каждой итерации выделяется свой фрейм памяти. Т.ч. алгоритм строго говоря рекурсивный, и не оптимальный. Это хорошо, ибо в таком виде он более понятен для разных жаба/php-обезьян. Сишник такую рекурсию разворачивает ещё в подкорке. Но тебе видимо не осмыслить программирование без std::append(), потому конструкция вроде *s++ для тебя «опасная» и «непонятная».

Ну и не важно, какой там код, хороший или плохой.

«хорошесть» кода зависит от ЯП и от задачи. Это явно не чистая сишечка, а какой-нить пхп. Там такое можно и нужно. Бантик красив на маленькой девочке, а на моей башке будет выглядеть нелепо. Всё зависит от контекста.

а разве где-то в продакшене используются примитивные структуры вроде бинарного дерева написанные на схеме?

Пишут, что здесь: http://www.getkahu.com/ Реализация Scheme под названием Racket

покажи мне там скажем красно-чёрное дерево. Ну или qsort.

когда ты будешь использовать «раскручивать» ранее накопленные промежуточные результаты.

То есть любой калькулятор, использующий стеки данных и операций для обработки скобок и порядка операций также является рекурсивным процессом? Несмотря на то, что машинный стек такой калькулятор использовать не может, так как ему надо два стека.

А ещё любая программа на FORTH'е...

А на википедии написано: факториал — произведение всех натуральных чисел от 1 до n включительно.

на самом деле у факториала есть несколько определений. Вот ещё одно:

n! <= (n-1)! * n; /n > 1/

n! <= 1; /n <= 1/

и это определение даёт более короткий, простой, и понятный код.Который не требует костылей типа for/fold и in-range.

Если то, что я написал кажется вам глупостью, просто проходите мимо

если кто-то знает ответ на мой вопрос, просто проходите мимо

поправил. прохожу

Ты, баття, попой не верти, скажи прямо - ты все еще веришь, что стек «быстрее» произвольного массива?

покажи мне там скажем красно-чёрное дерево

внутри http://pre.racket-lang.org/racket/collects/mred/private/wx/common/rbtree.rkt

Для пользователей: http://planet.racket-lang.org/package-source/krhari/pfds.plt/1/4/planet-docs/...

qsort

С учётом того, что списки там чаще, чем вектора, там сортировка слиянием.

и это определение даёт более короткий, простой, и понятный код.

Зависит от стандартной библиотеки.

Или хочешь сказать, что

(define (fact n) (if (> n 1) (* (fact (- n 1)) n) 1))

Читается проще, чем

(define (fact n) (apply * (range 1 n)))

(если уж мы не про производительность, а про читаемость)?

Т.ч. алгоритм строго говоря рекурсивный, и не оптимальный.

Вот она, квинтэссенция маразма - рекурсивный значит выделяющий память. Браво!

Это хорошо, ибо в таком виде он более понятен для разных жаба/php-обезьян. Сишник такую рекурсию разворачивает ещё в подкорке. Но тебе видимо не осмыслить программирование без std::append(), потому конструкция вроде *s++ для тебя «опасная» и «непонятная».

Твой уровень аргументации просто фееричен. Не важно, хороший это код или плохой, важен твой ответ на вопрос, рекурсивен ли он.

Нет, конечно. Это «руками» организованная рекурсия.

При итерации количество памяти, которая требуется для организации вычислений (не для самих вычислениях, а только для их организации, заметь) константа, при рекурсии - растет с n. У тебя при выделении памяти под дерево она растет с n, так что это рекурсия.Когда конкретон ты память выделяешь - не важно.

В первом случае необходимый кусок памяти, который надо выделить, никак не зависит от данных - надо выделить память для i и на этом все. Во втором случае для каждого набора данный нужно свое определенное количество памяти.

Потому что в первом случае res не используется как стек, очевидно.

Рекурсивный алгоритм не просто работает со стеком - он работает со стеком вполне определенным образом. В частности рекурсивный алгоритм не имеет права выделять стекфреймы «по частям» или эмулировать подобное выделение «руками».

Программа сама по себе не является рекурсивным или итеративным процессом. Рекурсивной может быть функция, поскольку она выражается сама через себя(при этом она может порождать итеративный процесс). Рекурсивным может быть алгоритм(если он описан через самого себя). Программа может порождать рекурсивный или итеративный процесс. Рекурсивный процесс накапливает промежуточные вычисления и потом выполняет некоторые «отложенные» вычисления при раскрутке некоторого «стека», итеративный же процесс просто переходит от одной фактически независимой итерации к другой. Можно начать итеративный процесс с любого шага.

Я думаю, что дело в том, что вам тут уже устали вдалбливать с разных сторон. Осильте хотя бы SICP(элементарщина же), тут даже ссылку привели на нужную главу....