История изменений
Исправление
dave,
(текущая версия)
:
Стек есть, но хвостовая рекурсия оптимизируется компилятором в обычный цикл.
Оптимизируется в цикл, но не в цикл самого хаскеля, а в цикл некой исполняющей машины! Это очень важный момент в понимании хвостовой рекурсии. Например, в Scala нет полноценной оптимизации хвостовой рекурсии, и, скорее всего, никогда там не будет. А вот в хаскеле есть!
По теме.
Итого. Рекурсия есть. Стек тоже есть. Еще есть _настоящая_ оптимизация хвостового вызова (Tail Call Optimisation - TCO). До кучи еще есть и ленивая стратегия вычисления благодаря тому, что язык ссылочно-прозрачный.
Факториал можно вычислять по-разному. Есть примитивная рекурсия в-лоб, которая выглядит хреново, а есть рекурсия через использование аккумулятора, причем хвостовая, которая дает прекрасные результаты.
Язык лучше изучать не в интернете, а читая книги. Не так давно для начинающих вышла отличная книга «Get Programming with Haskell», которая переведена на русский одним очень уважаемым хаскелистом и преподавателем (а не переводчиком, далеким от программирования).
Исходная версия
dave,
:
Стек есть, но хвостовая рекурсия оптимизируется компилятором в обычный цикл.
Оптимизируется в цикл, но не в цикл самого хаскеля, а в цикл некой исполняющей машины! Это очень важный момент в понимании хвостовой рекурсии. Например, в Scala нет полноценной оптимизации хвостовой рекурсии, и, скорее всего, никогда там не будет. А вот в хаскеле есть!
По теме.
Итого. Рекурсия есть. Стек тоже есть. Еще есть оптимизация хвостового вызова (Tail Call Optimisation - TCO). До кучи еще есть и ленивая стратегия вычисления благодаря тому, что язык ссылочно-прозрачный.
Факториал можно вычислять по-разному. Есть примитивная рекурсия в-лоб, которая выглядит хреново, а есть рекурсия через использование аккумулятора, причем хвостовая, которая дает прекрасные результаты.
Язык лучше изучать не в интернете, а читая книги. Не так давно для начинающих вышла отличная книга «Get Programming with Haskell», которая переведена на русский одним очень уважаемым хаскелистом и преподавателем (а не переводчиком, далеким от программирования).