Как и когда происходит рекурсия

Рекурсия появляется когда вызов функции повторно вызывает ту же функцию до завершения первоначального вызова функции. Например, рассмотрим известное математическое выражение x! (т.е. факториал). Факториал определяется для всех неотрицательных целых чисел следующим образом:



Если число равно 0, то будет 1.

В противном случае ответом будет то, что число умножается на факториал на единицу меньше этого числа.



В Python наивная реализация факториала может быть определена как функция следующим образом:

def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)



Иногда функции рекурсии трудно понять, поэтому давайте рассмотрим поэтапно. Рассмотрим выражение factorial(3). Эта и все остальные вызовы функций создают новую среду. Среда представляет собой таблицу, которая сопоставляет идентификаторы (например, n, factorial, print и т.д.) с их соответствующими значениями. В любой момент времени вы можете получить доступ к текущей среде с помощью locals(). В первом вызове функции единственная локальная переменная, которая определяется n = 3 . Поэтому locals() будет показывать {"n": 3}. Так как n == 3, возвращаемое значение становится n * factorial(n - 1).



На следующем этапе ситуация может немного запутаться. Глядя на наше новое выражение, мы уже знаем, что такое n. Однако мы еще не знаем, что такое factorial(n - 1). Во-первых, n - 1 принимает значение 2 . Затем 2 передаётся factorial как значение для n. Поскольку это новый вызов функции, создаётся вторая среда для хранения нового n. Пусть A — первое окружение, а B — второе окружение. A всё ещё существует и равен {"n": 3} , однако B (что равно {"n": 2}) является текущей средой. Если посмотреть на тело функции, возвращаемое значение, опять же, n * factorial(n - 1). Не определяя это выражение, заменим его на исходное выражение return. Делая это, мы мысленно отбрасываем B, поэтому не забудьте заменить n соответственно (т.е. ссылки на B n заменены на n - 1) который использует A n ). Теперь исходное обратное выражение становится n * ((n - 1) * factorial((n - 1) - 1)). Подумайте, почему так?



Теперь давайте определим factorial((n - 1) - 1)). Так как A n == 3, мы пропускаем 1 через factorial. Поэтому мы создаем новую среду C, которая равна {"n": 1}. Мы снова возвращаем значение n * factorial(n - 1). Итак, заменим исходный factorial((n - 1) - 1)) выражения return аналогично тому, как раньше мы скорректировали исходное выражение return. Исходное выражение теперь n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1))).



Почти закончили. Теперь нам нужно оценить factorial((n - 2) - 1). На этот раз мы пропустим через 0. Следовательно, должно получиться 1. Теперь давайте проведём нашу последнюю замену. Исходное выражение return теперь n * ((n - 1) * ((n - 2) * 1)). Напомню, что исходное выражение возврата оценивается под A , выражение становится 3 * ((3 - 1) * ((3 - 2) * 1)). Здесь получается 6. Чтобы убедиться, что это правильный ответ, вспомните, что 3! == 3 * 2 * 1 == 6. Прежде чем читать дальше, убедитесь, что вы полностью понимаете концепцию среды и то, как они применяются к рекурсии.



Утверждение, if n == 0: return 1, называется базовым случаем. Потому что это не рекурсия. Базовый случай необходим, без него вы столкнетесь с бесконечной рекурсией. С учетом сказанного, если у вас есть хотя бы один базовый случай, у вас может быть столько случаев, сколько вы хотите. Например, можно записать факториал таким образом:



def factorial(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return n * factorial(n - 1)



У вас может также быть несколько случаев рекурсии, но мы не будем вдаваться в подробности, потому что это редкий случай, и его трудно мысленно обрабатывать.



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

Если число равно 0, то ответ равен 0.

Если число равно 1, то ответ равен 1.

В противном случае ответ представляет собой сумму двух предыдущих чисел Фибоначчи.



Мы можем определить это следующим образом:

def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n - 2) + fib(n - 1)

Я не буду разбирать эту функцию также тщательно, как и с factorial(3), но окончательное значение возврата fib(5) эквивалентно следующему (синтаксически недействительному) выражению:

(
fib((n - 2) - 2)
+
(
fib(((n - 2) - 1) - 2)
+
fib(((n - 2) - 1) - 1)
)
)
+
(
(
fib(((n - 1) - 2) - 2)
+
fib(((n - 1) - 2) - 1)
)
+
(
fib(((n - 1) - 1) - 2)
+
(
fib((((n - 1) - 1) - 1) - 2)
+
fib((((n - 1) - 1) - 1) - 1)
)
)
)



Решением (1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1))) будет 5.



Теперь давайте рассмотрим еще несколько терминов:



Хвост вызова — это просто вызов рекурсивной функции, который является последней операцией и должна быть выполнена перед возвратом значения. Чтобы было понятно, return foo(n - 1) — это хвост вызова, но return foo(n - 1) + 1 не является (поскольку операция сложения будет последней операцией).

Оптимизация хвоста вызова (TCO) — это способ автоматического сокращения рекурсии в рекурсивных функциях.

Устранение хвоста вызова (TCE) - это сокращение хвостового вызова до выражения, которое может быть оценено без рекурсии. TCE — это тип TCO.



Оптимизация хвоста вызова может пригодиться по нескольким причинам:

Интерпретатор может снизить объём памяти, занятый средами. Поскольку ни у кого нет неограниченной памяти, чрезмерные рекурсивные вызовы функций приведут к переполнению стека.

Интерпретатор может уменьшить количество переключателей кадров стека.



В Python нет TCO по нескольким причинам, поэтому для обхода этого ограничения можно использовать другие методы. Выбор используемого метода зависит от варианта использования. Интуитивно понятно, что factorial и fib можно относительно легко преобразовать в итеративный код следующим образом:

def factorial(n):
product = 1
while n > 1:
product *= n
n -= 1
return product

def fib(n):
a, b = 0, 1
while n > 0:
a, b = b, a + b
n -= 1
return a



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



Другим полезным инструментом является декодер lru_cache, который можно использовать для уменьшения количества лишних вычислений.



Теперь вы знаете, как избежать рекурсии в Python, но когда её нужно использовать? Ответ «не часто». Все рекурсивные функции могут быть реализованы итеративно. Это просто вопрос, как именно сделать. Однако есть редкие случаи, когда можно использовать рекурсию. Рекурсия распространена в Python, когда ожидаемые вводы не вызовут значительного количества вызовов рекурсивных функций.



Если вы интересуетесь рекурсией, стоит изучить функциональные языки, такие как Scheme или Haskell. На таких языках рекурсия намного полезней.



Хотя приведённый выше пример последовательности Фибоначчи, хорошо показывает, как применять определение в python и позже использовать кэш lru, при этом он имеет неэффективное время работы, из-за того, что выполняет 2 рекурсивных вызова. Количество вызовов функции растет экспоненциально до n.

В таком случае лучше использовать линейную рекурсию:

def fib(n):
if n <= 1:
return (n,0)
else:
(a, b) = fib(n - 1)
return (a + b, a)



Но у этого примера есть проблема в возвращении пары чисел. Это показывает, что не всегда стоит использовать рекурсию.