Показать сообщение отдельно
Старый 10.02.2017, 23:24   #50  
Андре is offline
Андре
Moderator
Сотрудники компании GMCS
 
2,374 / 451 (20) +++++++
Регистрация: 03.12.2001
Цитата:
и получаем линейное, а не экспоненциальное время выполнения. и никаких повторных вычислений.
правда без "оптимизации хвостовой рекурсии" рекурсивные вызовы ограничены размером стека. а с оптимизацией стек вообще расти не будет.
так?
Да. Я правда подозреваю, что хороший оптимизатор это в цикл преобразует.

Цитата:
а разве функциональный язык не разворачивает всю эту байду в символьное супер-выражение, которое будет вычислено на самом последнем этапе?
Зависит от языка. Есть языки где вообще нет ленивых вычислений. Есть языки, где можно "включить" ленивость используя специальные выражения (ключевое слово lazy в F#), есть языки где все лениво по умолчанию (Haskell).
За это сообщение автора поблагодарили: mazzy (2).