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

[Андре]

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

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)) достаточно хранить только три числа.

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