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

[Андре]

Цитата:

Рекурсия для Фибоначчи?
Без дополнительного кэширования полученных результатов?
И без дополнительных комментариев почему именно так?

мне бы тоже не понравилось.

Обычно подобные задачи решают рекурсивно на функциональных языках разработки с оптимизации хвостовой рекурсии. В этом случае стек не будет использоваться и его переполнения не произойдет. А кеширование достигается посредством memoization (не возьмусь сказать, как это называется на русском).

Если не ошибаюсь, подобная задача расбирается в одной из первых глав классической книги "Структура и интерпретация компьютернах программ".

[mazzy]

Цитата:

Сообщение от Андре

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

тут дело даже не в функциональном языке или процедурном.
тут дело в ленивых вычислениях.
ну и отсутствие побочных эффектов, принятое в функциональных языках (если не увлекаться монадами, конечно)

именно ленивые вычисления и отсутствие побочных эффектов и позволяют так легко использовать рекурсию.

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

memcaсhe конечно спасает отца русской демократии во многих случаях. но обычно за счет непомерно увеличенного потребления памяти.
так скорее всего, в функциональном языке придется хранить все числа последовательности. или алгоритм будет каким-то безумным.

обрати внимание, что для линейной оценки времени выполнения достаточно хранить только два числа последовательности Фибонначи. а для меньшей оценки (f(n) < On(n)) достаточно хранить только три числа.

[mazzy]

Предыдущий мой пост зачеркнуть и забыть.

Цитата:

Сообщение от Андре

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

может, просто приведешь пример?
и объяснишь про "оптимизацию хвостовой рекурсии" для ряда чисел Фибоначчи?

ну, или ссылки хотя бы )))

[Андре]

Когда функция вызвает другую функцию (себя, как частный случай) она кладет на стек (который имет фиксированный и довольно небольшой размер) переменные, которые надо передать в функцию, и адрес возврата.

В рекурсивных программах глубина рекурсии может быть большой и стек может "внезапно переполнится". Если компилятор поддерживает оптимизацию хвостовой рекурсии и мы правильно написали программу (оба момента важны - не любую рекурсию можно оптимизировать), то мы можем избежать использования стека.

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

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

[mazzy]

Цитата:

Сообщение от Андре

не любую рекурсию можно оптимизировать

именно.

Цитата:

Сообщение от Андре

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

Именно.

А можно попросить рассказать применительно к ряду чисел Фибоначчи?

[Андре]

А можно на примере факториала ? У меня просто слайды остались с одного из докладов http://www.evernote.com/l/ABEfDwoBJN...J5KRvLmJcd7RA/ (на примере F#). Там как раз показан неочивидный момент, когда рекурсия не может быть оптимизирована.

[mazzy]

Не-а. ))))))
Для факториала как раз замечательно выполняется оптимизация хвостовой рекурсии даже вручную.

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

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

[Андре]

Она и для фибоначчи замечательно выполняется:

(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))))

[mazzy]

Цитата:

Сообщение от Андре

Она и для фибоначчи замечательно выполняется:

(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))))

ленивые функциональщики ))))
собственно возвращаемся к моему посту:

Цитата:

Сообщение от mazzy

тут дело даже не в функциональном языке или процедурном.
тут дело в ленивых вычислениях.
...
именно ленивые вычисления и отсутствие побочных эффектов и позволяют так легко использовать рекурсию.
...
обрати внимание, что для линейной оценки времени выполнения достаточно хранить только два числа последовательности Фибонначи. а для меньшей оценки (f(n) < On(n)) достаточно хранить только три числа.

А в функциональном языке ленивое выражение (+ a b) будет в стеке n раз ))))
и вот я совсем не уверен, что оптимизация сработает с таким выражением.

И именно эта ленивость и позволяет избавиться от повторных вычислений, не так ли? ленивость и отсутствие побочных эффектов.

Если бы подобная ленивость была бы в обычном языке, то...
Сейчас в .net вводят LINQ и Lazy-интерфейсы... это конечно не то, но достаточно близко...

можешь рассказать подробнее как "это" работает?

Цитата:

Сообщение от Андре

Так ты хотел узнать что такое оптимизация хвостовой рекурсии или устроить мне собеседование? Если первое - я постарался ответить.

Спасибо что ответил.

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

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

[Андре]

И, извини, но я все-таки спрошу:

Цитата:

может, просто приведешь пример?
ну, или ссылки хотя бы )))

Цитата:

Для факториала как раз замечательно выполняется оптимизация хвостовой рекурсии даже вручную. На собеседовании могут давать факториал, а могут давать фибоначчи ))))
....
бывает, конечно, когда кандидат не врубается и предлагает "удалиться".
что ж... в этом случае вряд ли такому кандидату стоит задавать другие вопросы.

Так ты хотел узнать что такое оптимизация хвостовой рекурсии или устроить мне собеседование? Если первое - я постарался ответить.

[Андре]

Цитата:

А в функциональном языке ленивое выражение (+ a b) будет в стеке n раз ))))
и вот я совсем не уверен, что оптимизация сработает с таким выражением.

И именно эта ленивость и позволяет избавиться от повторных вычислений, не так ли? ленивость и отсутствие побочных эффектов.

Нет! При чем тут ленивость и при чем тут побочные эффекты.

Половина функциональных языков программирования принципиально не поддерживают ленивость. Вот от слова "вообще". Нет ее там. А в тех языках где есть - я 10 раз подумаю, прежде чем ее использовать. Потому что в языках с поддержкой ленивых вычислений надо четко представлять, где и в какой момент это вычисление произойдет. А иначе оно произойдет в самый непоходящий для пользователя момент (в виде проблем с производительностью). Нет в моем примере никакой ленивости.

Теперь побочные эффекты. Их здесь нет, но если этот код переписать на C# или Java - их тоже не появится. Им просто не откуда здесь взяться. Ну и вообще, если говорить про функциональные языки программирования - то из тех, что используются в production я знаю только 1 - haskell. Все остальные функциональные языки программирования допускают побочные эффекты.

Цитата:

А в функциональном языке ленивое выражение (+ a b) будет в стеке n раз ))))

В языке с поддержкой хвостовой ресурсии - не будет.

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

Цитата:

можешь рассказать подробнее как "это" работает?

Да вроде уже максимально подробно. Смотри - при вызове функции ты на стек помещаешь 4 вещи: адрес возрата и три параметра. Теперь происходит очередной рекурсивный вызов. По идее компилятор должен положить еще 4 параматера. Но он умный и видит, что после того, как ты вернешься из этого рекурсивного вызова то, что до этого лежало на стеке тебе просто уже не понадобится. Ну просто потому что после рекурсивного вызова уже нет никаких вычисленией. А значит текущие значения a, b и count можно смело снять со стека, заменив на новые.

Все равно не понятно ?

[Ace of Database]

Получается, что тот кусок кода, который я написал вчера ночью за две минуты, укладывая сына спать, не имея Аксапты под рукой, добавил мне минус в карму?

[mazzy]

Цитата:

Сообщение от Ace of Database

Получается, что тот кусок кода, который я написал вчера ночью за две минуты, укладывая сына спать, не имея Аксапты под рукой, добавил мне минус в карму?

не знаю. это вам решать.

ваш кусок кода выполняет вычисления за один проход без повторных вычислений. что является достижением. и потребляет фиксированную память.
вот только int32 и панковский while(true)... ну и int2str...
живите теперь с этим. ))))

[Ace of Database]

Цитата:

Сообщение от mazzy

не знаю. это вам решать.
вот только int32 и панковский while(true)... ну и int2str...
живите теперь с этим. ))))

Нет, теперь я отрекусь от этого! Я постоянно меняюсь.

[Андре]

Можно еще вот так попробовать расписать - вызовы функций, как они будут происходить

fib 5
fib-iter 1 0 5
fib-iter 1 1 4
fib-iter 2 1 3
fib-iter 3 2 2
fib-iter 5 3 1
fib-iter 8 5 0
-> 5

То есть, мы вызываем fib 5, оно вызывает fib-iter 1 0 5, оно вызывает fib-iter 1 1 4 и так далее, пока вызов fib-iter 8 5 0 не вернет 5-ку.

Обрати внимание, что каждый последующий вызов - он самодостаточен. То есть. когда fib-iter 8 5 0 вернет 5-ку ему эту 5-ку надо просто вернуть, а не делать с ней что-то еще вверх по стеку вызовов. Это потому, что у нас последний вызов в функции выглядит так:

(fib-iter (+ a b) a (- count 1))))

А вот если бы он выглядел как то так

a + (fib-iter (+ a b) a (- count 1))))

то рекурсию нельзя было бы оптимизировать. Так как при последнем рекурсивном вызове полученную 5-ку надо была вернуть вверх по стеку, чтобы сложить вот с этой 'a'. И так далее.

Вот. Все - лучше мне уже на форуме не объяснить

p.s.

Цитата:

И именно эта ленивость и позволяет избавиться от повторных вычислений, не так ли?

А повторных вычислений здесь нет, потому что алгоритм так написан. Ну, их просто не надо делать, как и том примере с циклом.

Цитата:

обрати внимание, что для линейной оценки времени выполнения достаточно хранить только два числа последовательности Фибонначи. а для меньшей оценки (f(n) < On(n)) достаточно хранить только три числа.

Вот - вот. Я собственно это и делаю (см выше стек вызовов, что я привел). Просто совместил это с рекурсией, которая при этом еще и хвостовая

[mazzy]

Цитата:

Сообщение от Андре

Это потому, что у нас последний вызов в функции выглядит так:

(fib-iter (+ a b) a (- count 1))))

А вот если бы он выглядел как то так

a + (fib-iter (+ a b) a (- count 1))))

то рекурсию нельзя было бы оптимизировать.

ааааааа. так вот почему ты передаешь два аргумента, где первый может потеряться...

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

public var fib(var n)
{
   fibb-iter(1, 0, n);
}

private var fib-iter(var a, var b, var n)
{
   if(n <= 0)
      return b;
   else
      return fib-iter(a+b, b, n-1);
}

и получаем линейное, а не экспоненциальное время выполнения. и никаких повторных вычислений.
правда без "оптимизации хвостовой рекурсии" рекурсивные вызовы ограничены размером стека. а с оптимизацией стек вообще расти не будет.
так?

чертовы функциональщики... )))))

а разве функциональный язык не разворачивает всю эту байду в символьное супер-выражение, которое будет вычислено на самом последнем этапе?

[mazzy]

Цитата:

Сообщение от mazzy

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

Интересно, а как Silence свою рекурсию написал?
может, зря я на него бочку качу...

Цитата:

Сообщение от Silence

ЗЫ. Помню дали задачку, вывести ряд Фибоначи. Нарисовал рекурсию. Не понравилось. Видать не поняли.

[Ace of Database]

Маззи, пожалуйста не приводите мой код как пример дешевого программиста
Я выскочка с гуманитарным образованием.
Для людей с неправильным происхождением свойственно натыкаться на грабли на пути к совершенству. Сейчас я понял, что моя вчерашняя попытка написать пример была ошибкой. Но из-за некоторых таких попыток мне все-таки удалось кое-чего достичь в жизни. И я пока еще выживаю в конкурентной борьбе.
Я готов быть аутсайдером в окружении богов.
Готов получать 500 тыс рублей среди людей, которые получают миллион рублей.
Поэтому и встреваю в беседы великих

[Андре]

Цитата:

и получаем линейное, а не экспоненциальное время выполнения. и никаких повторных вычислений.
правда без "оптимизации хвостовой рекурсии" рекурсивные вызовы ограничены размером стека. а с оптимизацией стек вообще расти не будет.
так?

Да. Я правда подозреваю, что хороший оптимизатор это в цикл преобразует.

Цитата:

а разве функциональный язык не разворачивает всю эту байду в символьное супер-выражение, которое будет вычислено на самом последнем этапе?

Зависит от языка. Есть языки где вообще нет ленивых вычислений. Есть языки, где можно "включить" ленивость используя специальные выражения (ключевое слово lazy в F#), есть языки где все лениво по умолчанию (Haskell).

[Ace of Database]

Маззи, а как вам такой вариант?

static void Job46(Args _args)
{
     int j;
     
     real fibonaci(int n)
     {
        real    first = 0;
        real    second = 1;
        real    result = 0;
        int     i;
        for (i = 0; i < n; i++)
        {
            result = first + second;
            second = first;
            first = result;
        }
        return result;
    }
    ;
    for (j = 0; j < 50; j++)
    {
        info(strfmt("%1", fibonaci(j)));
    }
}