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

Содержание и основные понятия

Рекурсивная функция содержит базовый случай и переход к меньшей задаче. Ответ собирается при обратном сворачивании стека.
суть и практика
11 класс
ЕГЭ №16
01
Как это устроено
Рекурсия решает задачу через меньшую версию этой же задачи. Для корректности нужны база, уменьшающийся аргумент и понятное сворачивание результата.
База.
Случай, который возвращает ответ без нового вызова.
Переход.
Рекурсивный вызов с аргументом, приближающимся к базе.
Сворачивание.
После базы значения возвращаются по стеку в обратном порядке.
Стоимость.
Один рекурсивный вызов часто линейный; два ветвящихся могут дать экспоненциальное число вызовов.
02
Один пример в исполнении
Запусти короткую программу и переходи по строкам. Визуализатор показывает только код, текущую строку, переменные и вывод.
Рекурсивный факториал для n >= 0 имеет базу
n <= 1
и переход
n * factorial(n - 1)
. Если аргумент не уменьшается или база недостижима, Python завершит работу с
RecursionError
. Для повторяющихся ветвей, как в Fibonacci, используют мемоизацию: словарь сохраняет уже вычисленные значения и убирает повторную работу.
Карта алгоритма
Читай слева направо, затем запускай код.
1
Начало
2
Вызвать f(3)
3
n <= 1?
4
Нет: вызвать f(n - 1)
5
Вернуть произведение и вывести
03
Запомнить
Проверь базу на минимальном допустимом n.
Докажи, что каждый рекурсивный путь приближается к базе.
Не применяй наивную ветвящуюся рекурсию к большим n без мемоизации.
Синтаксис этой страницы
def f(n)
Определяет рекурсивную функцию.
if base: return
Базовый случай останавливает ветвь рекурсии.
f(n - 1)
Рекурсивный переход с уменьшающимся аргументом.
RecursionError
Исключение при слишком глубокой рекурсии или недостижимой базе.
dict.get(key, default)
В мемоизации читает сохранённый ответ или значение по умолчанию.
lru_cache
Декоратор functools для мемоизации; используй после понимания ручного состояния.
print
Показывает окончательно свёрнутый результат.
global calls
Разрешает функции изменять имя уровня модуля; применяй только для учебной трассы побочного счётчика.
calls += 1
Увеличивает счётчик вызовов на единицу.