Тут вышла статья на хабре [1], где написано:
"Хвостовая рекурсия это частный случай рекурсии, когда рекурсивный вызов может быть заменен итерацией."
Я почему-то всегда считал, что хвостовая рекурсия сложнее. Применительно к F# можно взять такой контр-пример.
Возьмем реализацию оператора while для F# Async. В исходниках F# это будет функция whileA. Если считать, что bindA - это монадическая связка для Async, то видим, что:
1) функция whileA вызывает bindA и передает последней вызов на саму себя, т.е. whileA определяется рекурсивно;
2) функции whileA и bindA используют хвостовые вызовы.
Отсюда можно заключить, что имеем случай хвостовой рекурсии (я прав в терминах?). При этом очевидно, что ни о какой замене whileA итерацией не может быть и речи, как минимум, в терминах .NET. Нужна соответствующая поддержка со стороны виртуальной машины.
В данном случае все хвостовые вызовы внутри whileA и bindA будут помечены в IL специальным тегом, который опознается виртуальной машиной .NET. Это ощутимо замедляет выполнение кода, но стек вызовов не увеличивается, что и требуется.
Так вот, имеем случай хвостовой рекурсии, несводимой к простой итерации в рамках .NET. Может быть, виртуальная машина и использует итерации, но это уже совсем другой внешний уровень.
[1] http://habrahabr.ru/post/143690/
> Так вот, имеем случай хвостовой рекурсии, несводимой к простой итерации в рамках .NET.
ОтветитьУдалитьЭто проблемы .NET, а не хвостовой рекурсии.
Сам .NET здесь упомянут постольку поскольку. Проблема более общая. Посыл же в том, что мы должны выйти за рамки некой вычислительной системы, чтобы на внешнем уровне уже реализовать хвостовую рекурсию. Другой вариант - переписать код через тот же трамплин, но это будет уже другой алгоритм и другой код.
ОтветитьУдалитьи все-таки это именно проблема .NET, а не рекурсии;) вообще, эта тема весьма подробно рассматривается в SICP'е (а ноги, у цитаты из начала статьи, растут именно оттуда).
Удалитьесли коротко (свими словами и, наверняка не точно), хвостовая рекурсия - это частный случай рекурсии, когда возможна tail-call optimization (http://en.wikipedia.org/wiki/Tail-call_optimization). и тут важно понимать, что есть 2 уровня восприятия программы: на первом мы рассматриваем ее поведение (эдакая спецификация черного ящика), а на втором уже думаем об эффективности реализации используемых конструкций. так вот, даже без tco, на первом уровне хвостовая рекурсия ничем от итерации не отличается, кроме отличного (в некоторых языках) синтаксиса: они делают одно и то же. на втором же уровне, при наличии tco, хвостовая рекурсия оказывается еще и столь же эффективна, по расходу памяти (и времени), как и простая итерация.
а вы зарываетесь в детали на такой низкий уровень, где уже можно говорить, что бывает while-итерация, а бывает for-итерация, т.к. они могут компилироваться в разный код. какой в этом смысл?