Цитата:
Сообщение от
Андре
Это потому, что у нас последний вызов в функции выглядит так:
X++:
(fib-iter (+ a b) a (- count 1))))
А вот если бы он выглядел как то так
X++:
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);
}
и получаем линейное, а не экспоненциальное время выполнения. и никаких повторных вычислений.
правда без "оптимизации хвостовой рекурсии" рекурсивные вызовы ограничены размером стека. а с оптимизацией стек вообще расти не будет.
так?
чертовы функциональщики... )))))
а разве функциональный язык не разворачивает всю эту байду в символьное супер-выражение, которое будет вычислено на самом последнем этапе?