Показать сообщение отдельно
Старый 10.02.2017, 22:09   #43  
mazzy is offline
mazzy
Administrator
Аватар для mazzy
Most Valuable Professional
Лучший по профессии 2015
Лучший по профессии 2014
Лучший по профессии AXAWARD 2013
Лучший по профессии 2011
Лучший по профессии 2009
 
28,836 / 3725 (182) ++++++++++
Регистрация: 29.11.2001
Адрес: Москва
Цитата:
Сообщение от Андре Посмотреть сообщение
Она и для фибоначчи замечательно выполняется:

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-интерфейсы... это конечно не то, но достаточно близко...

можешь рассказать подробнее как "это" работает?

Цитата:
Сообщение от Андре Посмотреть сообщение
Так ты хотел узнать что такое оптимизация хвостовой рекурсии или устроить мне собеседование? Если первое - я постарался ответить.
Спасибо что ответил.

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

в свое время я тебя приглашал, но у тебя была более привлекательная работа.
до сих пор жалею, что тогда не смог предложить тебе лучшие условия.