Можно еще вот так попробовать расписать - вызовы функций, как они будут происходить
X++:
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-ку надо просто вернуть, а не делать с ней что-то еще вверх по стеку вызовов. Это потому, что у нас последний вызов в функции выглядит так:
X++:
(fib-iter (+ a b) a (- count 1))))
А вот если бы он выглядел как то так
X++:
a + (fib-iter (+ a b) a (- count 1))))
то рекурсию нельзя было бы оптимизировать. Так как при последнем рекурсивном вызове полученную 5-ку надо была вернуть вверх по стеку, чтобы сложить вот с этой 'a'. И так далее.
Вот. Все - лучше мне уже на форуме не объяснить
p.s.
Цитата:
И именно эта ленивость и позволяет избавиться от повторных вычислений, не так ли?
А повторных вычислений здесь нет, потому что алгоритм так написан. Ну, их просто не надо делать, как и том примере с циклом.
Цитата:
обрати внимание, что для линейной оценки времени выполнения достаточно хранить только два числа последовательности Фибонначи. а для меньшей оценки (f(n) < On(n)) достаточно хранить только три числа.
Вот - вот. Я собственно это и делаю (см выше стек вызовов, что я привел). Просто совместил это с рекурсией, которая при этом еще и хвостовая