Хвостовая рекурсия
Гоша: Значит, использовать рекурсию не очень эффективно? При вызове рекурсивной функции все операции сохраняются в стеке вызовов. Кроме этого, стек может переполниться, да?
Тимофей: Не всегда.
Есть особый тип рекурсии — хвостовая. Для неё это утверждение неверно.
Алла: А что значит хвостовая? У неё что, есть хвост?
Тимофей: Это особый тип рекурсии, при котором любой рекурсивный вызов — последняя операция перед возвратом из функции. Особенность в том, что такую рекурсию можно заменить на итерацию. Это делается для оптимизации программы. Такая возможность реализована во многих компиляторах.
В рекурсии стек помогает восстанавливать состояние вызывающей функции.
Но сохранять параметры и локальные переменные не нужно, если выполняются два условия:
- Рекурсивный вызов — это последняя операция перед выходом из вызывающей функции;
- Результат вызывающей функции — это результат, который возвращает рекурсивный вызов.
То есть можно заменить значения параметров в стеке и вернуть управление. Фактически — выполнить обычный цикл.
Тимофей: Ну как, понятно?
Гоша: Да, ещё бы!
Алла: А мне что-то не очень.
Тимофей: Давайте посмотрим на примерах.
Гоша: Лишним, конечно, не будет!
Дана функция:
Скопировать кодPYTHON
def f(x, y):
if y == 0:
return x
return f(2x * y, y - 1)
Это хвостовая рекурсивная функция, потому что последняя инструкция в вызывающей функции — рекурсивный вызов. И вызывающая функция возвращает результат этого вызова.
Рассмотрим другой пример:
Скопировать кодPYTHON
def f(x):
if x == 1:
return 1
y = f(x - 1)
return x * y + 1
А это не хвостовая рекурсивная функция, ведь после возврата из рекурсивного вызова выполняются некоторые вычисления.
Тимофей: Теперь стало понятнее?
Гоша: Даже Алла поняла, а я так и подавно!
Сейчас проверим. Вспомним функцию вычисление факториала:
Скопировать кодPYTHON
def factorial(n):
if n == 0 or n == 1:
return 1
return n * factorial(n - 1)