РЕКУРСИЯ В PYTHON

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

Пример — поиск факториала числа:

1
2
3
4
5

Разберём по шагам вызов find_factorial(4):

find_factorial(4)                     # n = 4, возвращает 4 * find_factorial(3)

  find_factorial(3)                   # n = 3, возвращает 3 * find_factorial(2)

    find_factorial(2)                 # n = 2, возвращает 2 * find_factorial(1)

      find_factorial(1)               # n = 1, базовый случай, возвращает 1

Теперь подставляем значения обратно:

find_factorial(1) = 1

find_factorial(2) = 2 * 1 = 2

find_factorial(3) = 3 * 2 = 6

find_factorial(4) = 4 * 6 = 24

Стек вызовов

Информация обо всех незавершённых функциях хранится в стеке. Стек — это структура данных, работающая по принципу «последний пришёл — первый ушёл» (LIFO). При этом в каждый момент времени работает только та функция, которая находится наверху стека.

В примере выше, когда мы вызвали find_factorial(4), стек заполнился четырьмя вызовами. Когда find_factorial(1) вернул 1, стек начал «разворачиваться» — каждая функция получила результат и вернула своё значение вверх по цепочке.

setrecursionlimit

setrecursionlimit — это функция в Python в библиотеке sys, которая позволяет установить максимальную глубину рекурсии, чтобы предотвратить переполнение стека и сбой программы. По умолчанию это значение равно 1000, но его можно увеличить, если ваш рекурсивный алгоритм требует большей глубины вложенности вызовов.

Например, вызов find_factorial(1111) даст ошибку:

RecursionError: maximum recursion depth exceeded

Решение — увеличить лимит:

from sys import setrecursionlimit

# Указываем максимально возможную глубину рекурсии

1
2
3
4
5
6
7
8
9

Примечание: setrecursionlimit не стоит использовать, если у вас слабый ПК или рекурсивный алгоритм очень медленно двигается (например: f(x) = f(x – 5) + f(x + 6))

lru_cache

@lru_cache в Python — это встроенный декоратор из модуля functools, который реализует алгоритм кэширования для ускорения работы функций. Он сохраняет результаты вызовов функций и, если вызывается с теми же аргументами, возвращает кэшированное значение, а не вычисляет его заново.

Пример — числа Фибоначчи. Без кэширования вызов fib(40) работает очень долго, потому что одни и те же значения считаются многократно. С @lru_cache результат мгновенный:

1
2
3
4
5
6
7
8
9
10
11

*Декораторы в Python — это специальные функции, которые позволяют добавлять к функциям и методам дополнительную логику, принимая их за аргумент. Исходные параметры при этом не затрагиваются.