Показать сообщение отдельно
Старый 10.02.2017, 23:13   #48  
mazzy is offline
mazzy
Участник
Аватар для mazzy
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
29,472 / 4494 (208) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Записей в блоге: 10
Цитата:
Сообщение от Андре Посмотреть сообщение
Это потому, что у нас последний вызов в функции выглядит так:

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);
}
и получаем линейное, а не экспоненциальное время выполнения. и никаких повторных вычислений.
правда без "оптимизации хвостовой рекурсии" рекурсивные вызовы ограничены размером стека. а с оптимизацией стек вообще расти не будет.
так?

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

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