Alterna · 38.3 — Рекурсивные алгоритмы

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

суть и практика11 классЕГЭ №16

Как это устроено

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

База. Случай, который возвращает ответ без нового вызова.

Переход. Рекурсивный вызов с аргументом, приближающимся к базе.

Сворачивание. После базы значения возвращаются по стеку в обратном порядке.

Стоимость. Один рекурсивный вызов часто линейный; два ветвящихся могут дать экспоненциальное число вызовов.

Один пример в исполнении

Запусти короткую программу и переходи по строкам. Визуализатор показывает только код, текущую строку, переменные и вывод.

Рекурсивный факториал для n >= 0 имеет базу n <= 1 и переход n * factorial(n - 1). Если аргумент не уменьшается или база недостижима, Python завершит работу с RecursionError. Для повторяющихся ветвей, как в Fibonacci, используют мемоизацию: словарь сохраняет уже вычисленные значения и убирает повторную работу.

Карта алгоритмаЧитай слева направо, затем запускай код.

1Начало
2Вызвать f(3)
3n <= 1?
4Нет: вызвать f(n - 1)
5Вернуть произведение и вывести

Запомнить

Проверь базу на минимальном допустимом n.
Докажи, что каждый рекурсивный путь приближается к базе.
Не применяй наивную ветвящуюся рекурсию к большим n без мемоизации.

Синтаксис этой страницы

def f(n)

Определяет рекурсивную функцию.

if base: return

Базовый случай останавливает ветвь рекурсии.

f(n - 1)

Рекурсивный переход с уменьшающимся аргументом.

RecursionError

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

dict.get(key, default)

В мемоизации читает сохранённый ответ или значение по умолчанию.

lru_cache

Декоратор functools для мемоизации; используй после понимания ручного состояния.

print

Показывает окончательно свёрнутый результат.

global calls

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

calls += 1

Увеличивает счётчик вызовов на единицу.