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

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

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

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

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

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