вторник, 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/

3 комментария:

  1. > Так вот, имеем случай хвостовой рекурсии, несводимой к простой итерации в рамках .NET.

    Это проблемы .NET, а не хвостовой рекурсии.

    ОтветитьУдалить
  2. Сам .NET здесь упомянут постольку поскольку. Проблема более общая. Посыл же в том, что мы должны выйти за рамки некой вычислительной системы, чтобы на внешнем уровне уже реализовать хвостовую рекурсию. Другой вариант - переписать код через тот же трамплин, но это будет уже другой алгоритм и другой код.

    ОтветитьУдалить
    Ответы
    1. и все-таки это именно проблема .NET, а не рекурсии;) вообще, эта тема весьма подробно рассматривается в SICP'е (а ноги, у цитаты из начала статьи, растут именно оттуда).

      если коротко (свими словами и, наверняка не точно), хвостовая рекурсия - это частный случай рекурсии, когда возможна tail-call optimization (http://en.wikipedia.org/wiki/Tail-call_optimization). и тут важно понимать, что есть 2 уровня восприятия программы: на первом мы рассматриваем ее поведение (эдакая спецификация черного ящика), а на втором уже думаем об эффективности реализации используемых конструкций. так вот, даже без tco, на первом уровне хвостовая рекурсия ничем от итерации не отличается, кроме отличного (в некоторых языках) синтаксиса: они делают одно и то же. на втором же уровне, при наличии tco, хвостовая рекурсия оказывается еще и столь же эффективна, по расходу памяти (и времени), как и простая итерация.

      а вы зарываетесь в детали на такой низкий уровень, где уже можно говорить, что бывает while-итерация, а бывает for-итерация, т.к. они могут компилироваться в разный код. какой в этом смысл?

      Удалить