Показать сообщение отдельно
Старый 10.02.2017, 22:33   #46  
Андре is offline
Андре
Moderator
Сотрудники компании GMCS
 
2,374 / 451 (20) +++++++
Регистрация: 03.12.2001
Можно еще вот так попробовать расписать - вызовы функций, как они будут происходить

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

Последний раз редактировалось Андре; 10.02.2017 в 22:41.
За это сообщение автора поблагодарили: mazzy (2).