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

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

Описание

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

Применение

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

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

Примеры

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

Scheme	C
(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) { if (n == 0) return acc; else return fac_times(n - 1, acc * n); } int factorial (int n) { return fac_times (n, 1); }

Контрпример

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

Scheme	C
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))	int factorial (int n) { if (n == 0) return 1; else return n * factorial(n - 1); }

См. также

• Стек
• Стековый кадр
• Переполнение буфера

Примечания

1. ↑ Paul E. Black, «tail recursion», 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. ↑ Revised⁵ Report on the Algorithmic Language Scheme (англ.) (Проверено 16 сентября 2010)