Хвостовая рекурсия
Хвостовая рекурсия — специальный случай рекурсии, при котором рекурсивный вызов функцией самой себя является её последней операцией.[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); } |
[править] См. также
[править] Примечания
- ↑ 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)
- ↑ Revised5 Report on the Algorithmic Language Scheme (англ.) (Проверено 16 сентября 2010)
 |
Это заготовка статьи о программировании. Вы можете помочь проекту, исправив и дополнив её. |
