Цитата:
Сообщение от
Андре
Она и для фибоначчи замечательно выполняется:
X++:
(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
ленивые функциональщики ))))
собственно возвращаемся к моему посту:
Цитата:
Сообщение от
mazzy
тут дело даже не в функциональном языке или процедурном.
тут дело в ленивых вычислениях.
...
именно ленивые вычисления и отсутствие побочных эффектов и позволяют так легко использовать рекурсию.
...
обрати внимание, что для линейной оценки времени выполнения достаточно хранить только два числа последовательности Фибонначи. а для меньшей оценки (f(n) < On(n)) достаточно хранить только три числа.
А в функциональном языке ленивое выражение (+ a b) будет в стеке n раз ))))
и вот я совсем не уверен, что оптимизация сработает с таким выражением.
И именно эта ленивость и позволяет избавиться от повторных вычислений, не так ли? ленивость и отсутствие побочных эффектов.
Если бы подобная ленивость была бы в обычном языке, то...
Сейчас в .net вводят LINQ и Lazy-интерфейсы... это конечно не то, но достаточно близко...
можешь рассказать подробнее как "это" работает?
Цитата:
Сообщение от
Андре
Так ты хотел узнать что такое оптимизация хвостовой рекурсии или устроить мне собеседование?
Если первое - я постарался ответить.
Спасибо что ответил.
не... я надеялся, что ты расскажешь всем. у тебя это хорошо получается.
кроме того, здесь есть и другие функциональщики, которые могут подключиться к обсуждению.
в свое время я тебя приглашал, но у тебя была более привлекательная работа.
до сих пор жалею, что тогда не смог предложить тебе лучшие условия.