вторник, 22 мая 2012 г.

О хвостовой рекурсии


Тут вышла статья на хабре [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/