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