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

[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);
}

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

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

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