Рекурсия и запоминание

Факториал 4 — это 4, умноженное на факториал 3. Сумма цифр числа — последняя цифра плюс сумма цифр остальных. Многие задачи сами сводятся к такой же задаче поменьше. Рекурсивная функция вызывает саму себя для меньшего случая; незавершённые вызовы ждут в стеке, а @cache запоминает уже найденные ответы. Каждый вызов — та же рамка, что в уроке о функциях, только рамки одной функции складываются стопкой. Алгоритмы на рекурсии разобраны в темах экзамена; здесь — механизм языка.

Проследим, как рекурсия считает факториал 4! = 1 · 2 · 3 · 4 = 24. Потом на числах Фибоначчи увидим цену повторных вычислений.

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

Факториал неотрицательного целого n — произведение чисел от 1 до n, причём 0! = 1. Отсюда n! = n * (n - 1)! при n > 0.

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

Ветка n == 0 — базовый случай, решаемый без дальнейшего обращения. Остальное — переход к меньшему случаю. Для корректности нужно убедиться, что переходы обязательно приводят к базе: n каждый раз уменьшается на 1 и от неотрицательного числа дойдёт до 0.

Каждый незавершённый вызов ждёт результата следующего и хранится в стеке вызовов. Для factorial(4) вызов ждёт результата factorial(3), тот — factorial(2), затем factorial(1) и factorial(0). После базы возвращения идут в обратном порядке: 1, 1, 2, 6, 24. Каждый вызов ждёт, пока ответит следующий: factorial(4) нужно 4 × результат для 3, factorial(3) — 3 × результат для 2, и так до factorial(0), который сразу знает ответ 1. Пошагово это выглядит так:

Каждый незавершённый вызов хранит собственные параметры и место продолжения. Эта последовательность хранится в стеке вызовов. Стек — структура «последним вошёл, первым вышел»: первым завершается самый глубокий вызов.

У Python ограничена глубина рекурсивных вызовов. Если базовый случай недостижим, стек переполняется:

def down(n):    return down(n - 1) down(5)

RecursionError означает, что вложенных вызовов стало больше допустимого. Узнать предел можно через стандартный модуль sys — набор средств для связи с интерпретатором. Он подключается так же, как math в уроке о модулях.

import sys print(sys.getrecursionlimit())

sys.setrecursionlimit(5000) поднимает предел. Без необходимости поднимать его до огромного числа нельзя считать исправлением алгоритма: стек и память конечны. Python не превращает рекурсию в цикл сам, поэтому для длинной цепочки вызовов обычно лучше написать цикл.

Прямая рекурсия может много раз вычислять одно и то же. Пусть последовательность задана как F(0) = 0, F(1) = 1, а далее F(n) = F(n - 1) + F(n - 2). Прямой рекурсивный код многократно вычисляет одинаковые значения. Например, при вычислении F(5) значение F(3) понадобится и прямо, и внутри F(4). Посчитаем вызовы:

calls = 0 def fibonacci_slow(n):    global calls    calls += 1    if n < 2:        return n    return fibonacci_slow(n - 1) + fibonacci_slow(n - 2) print(fibonacci_slow(20), calls)

global calls разрешает функции менять внешний счётчик. Для 21 различного значения F(0)…F(20) понадобилось почти 22 тысячи вызовов. Число вызовов растёт очень быстро: для n = 10 их 177, для 20 — 21 891, для 25 — 242 785, а для 30 — уже 2 692 537. Откуда столько? Вот все вызовы уже для F(5):

Мемоизация — сохранение результата для уже рассмотренных аргументов. При следующем таком же запросе результат берётся из памяти. В Python есть cache в стандартном модуле functools; from functools import cache подключает это имя:

from functools import cache @cachedef fibonacci(n):    if n < 2:        return n    return fibonacci(n - 1) + fibonacci(n - 2) print(fibonacci(10), fibonacci(90))

Строка @cache над def добавляет функции память: перед вычислением она ищет ответ для этого аргумента, а после — сохраняет его.

Теперь каждое F(k) вычисляется один раз: для F(n) нужно всего n + 1 разных вычислений. Поэтому F(90) считается мгновенно. Но глубина первого спуска остаётся линейной, а кэш хранит все результаты. Кэш не устраняет ограничения рекурсивной глубины.

Аргументы кэшируемой функции — числа, строки, кортежи; список передать нельзя. Результат должен определяться аргументами. Если функция зависит от изменяющейся глобальной переменной, файла или времени, кэш может возвращать устаревшие данные. Очистить его можно fibonacci.cache_clear().

Модуль «Функции» складывается в одну модель вызова. Вызов функции — это новая рамка со своими переменными (урок о функциях). В неё попадают аргументы — по позиции, по имени или значения по умолчанию, созданные один раз при def (урок о договорённости функции). Функции и имена можно брать из модулей (урок о модулях) и передавать другим функциям, как key сортировке (урок о сортировке). Незавершённые вызовы лежат стопкой — это и есть стек вызовов, а рекурсия лишь кладёт в стопку вызовы той же функции.

В пошаговом запуске это видно так: вызов добавляет новую рамку, где параметры уже связаны с аргументами; присваивание внутри меняет только верхнюю рамку; return убирает её и отдаёт значение в строку вызова. При рекурсии рамок одной функции становится несколько, и у каждой своё n.