Хвостовая рекурсия

Хвостовая рекурсия — частный случай рекурсии, при котором любой рекурсивный вызов является последней операцией перед возвратом из функции.[1] Подобный вид рекурсии примечателен тем, что может быть легко заменён на итерацию путём формальной и гарантированно корректной перестройки кода функции. Оптимизация хвостовой рекурсии путём преобразования её в плоскую итерацию реализована во многих оптимизирующих компиляторах. В некоторых функциональных языках программирования спецификация гарантирует обязательную оптимизацию хвостовой рекурсии.

Описание

Типовой механизм реализации вызова функции основан на сохранении адреса возврата, параметров и локальных переменных функции в стеке и выглядит следующим образом:

  1. В точке вызова в стек помещаются параметры, передаваемые функции, и адрес возврата.
  2. Вызываемая функция в ходе работы размещает в стеке собственные локальные переменные.
  3. По завершении вычислений функция очищает стек от своих локальных переменных, записывает результат (обычно — в один из регистров процессора).
  4. Команда возврата из функции считывает из стека адрес возврата и выполняет переход по этому адресу. Либо непосредственно перед, либо сразу после возврата из функции стек очищается от параметров.

Таким образом, при каждом рекурсивном вызове функции создаётся новый набор её параметров и локальных переменных, который вместе с адресом возврата размещается в стеке, что ограничивает максимальную глубину рекурсии объёмом стека. В чисто функциональных или декларативных (типа Пролога) языках, где рекурсия является единственным возможным способом организации повторяющихся вычислений, это ограничение становится крайне существенным, поскольку, фактически, превращается в ограничение на число итераций в любых циклических вычислениях, при превышении которого будет происходить переполнение стека.

Нетрудно видеть, что необходимость расширения стека при рекурсивных вызовах диктуется требованием восстановления состояния вызывающего экземпляра функции (то есть её параметров, локальных данных и адреса возврата) после возврата из рекурсивного вызова. Но если рекурсивный вызов является последней операцией перед выходом из вызывающей функции и результатом вызывающей функции должен стать результат, который вернёт рекурсивный вызов, сохранение контекста уже не имеет значения — ни параметры, ни локальные переменные уже использоваться не будут, а адрес возврата уже находится в стеке. Поэтому в такой ситуации вместо полноценного рекурсивного вызова функции можно просто заменить значения параметров в стеке и передать управление на точку входа. До тех пор, пока исполнение будет идти по этой рекурсивной ветви, будет, фактически, выполняться обычный цикл. Когда рекурсия завершится (то есть исполнение пройдёт по терминальной ветви и достигнет команды возврата из функции) возврат произойдёт сразу в исходную точку, откуда произошёл вызов рекурсивной функции. Таким образом, при любой глубине рекурсии стек переполнен не будет.

Применение

Хвостовая рекурсия часто применяется в программах на функциональных языках программирования. Многие вычисления на таких языках естественно выражать в виде рекурсивных функций, а возможность автоматической замены транслятором хвостовой рекурсии на итерацию означает, что по вычислительной эффективности она равна эквивалентному коду, записанному в итеративном виде.

Создатели функционального языка Scheme, одного из диалектов Lisp, оценили важность хвостовой рекурсии настолько, что в спецификации языка предписали каждому транслятору этого языка в обязательном порядке реализовывать оптимизацию хвостовой рекурсии и описали точный набор условий, которым должна отвечать рекурсивная функция, чтобы рекурсия в ней была оптимизирована.[2]

Примеры

Пример рекурсивной функции для вычисления факториала, использующей хвостовую рекурсию на языках программирования Scheme, C и Scala:

Scheme C Scala 
(define (factorial n)
  (define (fac-times n acc)
    (if (= n 0)
        acc
        (fac-times (- n 1) (* acc n))))
  (fac-times n 1))

int fac_times (int n, int acc) {
    return (n==0) ? acc : fac_times(n - 1, acc * n);
}
int factorial (int n) {
    return fac_times (n, 1);
}

@tailrec
def factorial(it: Int, result: Int = 1) : Int =
{
    if (it < 1)
        result
    else
        factorial(it - 1, result * it)
}

Проблемы

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

В качестве примера простой рекурсивной функции, которая не является хвостово-рекурсивной и не может быть автоматически преобразована в итеративную, можно привести наиболее очевидный рекурсивный способ вычисления факториала, который обычно приводят в учебниках как простейший пример рекурсивной функции:

Scheme C 
(define (factorial n)
  (if (= n 0)
      1
      (* n
         (factorial (- n 1)))))

int factorial (int n) {
    return (n==0) ? 1 : n*factorial(n-1);
}

В этом примере, несмотря на то, что рекурсивный вызов в тексте функции стоит на последнем месте, автоматической оптимизации рекурсии не получится, так как фактически последней выполняемой операцией является операция умножения на n, а значит условие хвостовой рекурсии не выполняется. Приведённые выше хвостово-рекурсивные варианты вычисления факториала являются модификацией очевидного способа, которая как раз и направлена на перенос операции умножения. Применённый для этого метод, кстати, является одним из типовых способов приведения рекурсии к хвостово-рекурсивному виду. Он заключается в том, что набор локальных данных, который нуждается в сохранении при рекурсивном вызове, переносится в параметры вызова функции. В случае с приведёнными примерами вычисления факториала таким параметром является переменная acc, в которой происходит накопление результата.

Вообще подобные модификации могут быть достаточно нетривиальными. В частности, возможен вариант, когда хвостово-рекурсивной делается только одна, наиболее «проблемная» ветвь исполнения функции, тогда как остальные остаются рекурсивными.

См. также

Примечания

  1. ↑ Paul E. Black, «tail recursion Архивная копия от 15 октября 2011 на Wayback Machine», in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 August 2008. (англ.) (Дата обращения: 6 октября 2011)
  2. ↑ Revised5 Report on the Algorithmic Language Scheme Архивная копия от 5 января 2007 на Wayback Machine (англ.) (Дата обращения: 16 сентября 2010)