Что такое рекурсия
Рекурсия — это техника, при которой функция вызывает саму себя для решения подзадачи. Каждая рекурсивная функция состоит из двух частей:
- Base case — условие остановки. Случай, который мы можем решить без обращения к рекурсии.
- Recursive step — шаг рекурсии. Случай, где мы сводим задачу к меньшей версии той же задачи.
Без base case рекурсия будет бесконечной и взорвёт стек. Без recursive step это уже не рекурсия. Обе части обязательны.
Классический пример — факториал. n! = 1 * 2 * 3 * ... * n. Рекурсивно это:
factorial(0) = 1— base case.factorial(n) = n * factorial(n - 1)— recursive step.
def factorial(n):
if n == 0:
return 1 # base case
return n * factorial(n - 1) # recursive step
print(factorial(5)) # 120Каждый вызов сводит задачу к меньшей. factorial(5) зовёт factorial(4), который зовёт factorial(3), и так до factorial(0). Потом стек разворачивается обратно, перемножая значения.
Каждый вызов делает один рекурсивный вызов до достижения base case. Глубина равна аргументу.
Когда рекурсия удобна
Рекурсия естественна для задач, в которых сама структура — рекурсивная:
- Деревья. Дерево состоит из узлов, каждый узел содержит поддеревья. Обход — это рекурсия.
- Графы (DFS). Поиск в глубину естественно записывается через рекурсию.
- Divide-and-conquer. Merge sort, quicksort, binary search — все они «разбей пополам и реши на половинах».
- Парсинг. Парсер JSON / выражений — естественно рекурсивный.
- Backtracking. Перебор с откатами — N-queens, sudoku — рекурсия с состоянием.
Если задача имеет структуру «решить большую через меньшие той же формы» — рекурсия подходит идеально. Если же задача — линейный проход с накапливаемым состоянием — итерация обычно лучше.
Фибоначчи: рекурсия без мемоизации
Числа Фибоначчи: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). Прямая рекурсивная реализация:
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(10)) # 55
print(fib(30)) # 832040 — заметная пауза
print(fib(40)) # очень долго, секундыПроблема: вычисление fib(40) занимает несколько секунд. fib(50) уже минуты. Почему? Потому что рекурсия здесь создаёт дерево вызовов, а не линейную цепочку:
fib(5)
├── fib(4)
│ ├── fib(3)
│ │ ├── fib(2)
│ │ │ ├── fib(1) = 1
│ │ │ └── fib(0) = 0
│ │ └── fib(1) = 1
│ └── fib(2)
│ ├── fib(1) = 1
│ └── fib(0) = 0
└── fib(3)
├── fib(2)
│ ├── fib(1) = 1
│ └── fib(0) = 0
└── fib(1) = 1Заметьте: fib(2) вычисляется три раза, fib(1) — пять раз. Полное число вызовов растёт как сами числа Фибоначчи: T(n) = F(n), экспоненциально. Это O(phi^n), где phi ~ 1.618. Для n = 40 это около 100 миллионов вызовов.
Мемоизация: O(2^n) превращается в O(n)
Мемоизация — это кеширование результатов уже вычисленных подзадач. Идея простая: если функция вызвана с теми же аргументами, вернуть кешированный ответ.
def fib_memo(n, cache=None):
if cache is None:
cache = {}
if n in cache:
return cache[n]
if n < 2:
return n
cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
return cache[n]
print(fib_memo(100)) # 354224848179261915075 — мгновенноТеперь каждое значение fib(k) вычисляется ровно один раз — итого O(n) вызовов. На 1000 раз быстрее на n = 40.
В Python есть встроенный декоратор:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(500)) # вычисляется за миллисекундыlru_cache хранит результаты в dict (где ключ — аргументы), и при повторном вызове возвращает кеш. Это decorator pattern — никак не меняет код функции, добавляет автоматический кеш.
Мемоизация превращает экспоненциальную сложность в линейную.
Анатомия рекурсивной функции
Шаблон корректной рекурсивной функции:
def recursive_function(arg):
# 1. Проверка base case
if base_condition(arg):
return base_value
# 2. Уменьшение задачи
smaller_arg = reduce(arg)
# 3. Рекурсивный вызов
sub_result = recursive_function(smaller_arg)
# 4. Комбинирование
return combine(arg, sub_result)Где могут быть ошибки:
- Забыли base case — бесконечная рекурсия, RecursionError или stack overflow.
- Base case не достижим — например, ждём
n == 0, но передаёмn - 2для нечётного n. Никогда не достигнем 0, упадём на отрицательных. - Не уменьшаем задачу —
recursive_function(arg)зовётrecursive_function(arg). Бесконечный цикл. - Не комбинируем результат — забыли использовать
sub_result, функция возвращает None или мусор.
Каждый рекурсивный вызов должен приближаться к base case. Это инвариант, который надо держать в голове.
Перед тем как писать рекурсию, проговорите вслух: “base case — это X. Recursive step — задача размера N сводится к задаче размера N-1 (или N/2) операцией Y.” Если не получается проговорить — рекурсия не подходит, нужна итерация.
Бинарный поиск рекурсивно
В прошлом модуле мы делали бинарный поиск итеративно. Рекурсивная форма:
def binary_search(xs, target, lo=0, hi=None):
if hi is None:
hi = len(xs)
# base case: пустой диапазон
if lo >= hi:
return -1
mid = lo + (hi - lo) // 2
# base case: нашли
if xs[mid] == target:
return mid
# recursive step: половина диапазона
if xs[mid] < target:
return binary_search(xs, target, mid + 1, hi)
return binary_search(xs, target, lo, mid)Логика та же, но граничные условия выражены как base case. Какая форма лучше — итеративная или рекурсивная? Для бинарного поиска большинство профессионалов выбирают итеративную:
- Глубина рекурсии log(n), что хорошо, но добавляет overhead на каждый вызов (создание stack frame).
- Итеративный код проще оптимизировать.
- В Python tail recursion не оптимизируется — об этом будет урок дальше.
Но для деревьев и графов рекурсия часто читается лучше — это вопрос натуральности структуры.
Замеры
Сравним рекурсивный fib без мемо, с мемо и итеративный:
import timeit
from functools import lru_cache
def fib_naive(n):
if n < 2:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
@lru_cache(maxsize=None)
def fib_memo(n):
if n < 2:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
n = 30
print(f"naive: {timeit.timeit(lambda: fib_naive(n), number=10):.3f} s")
print(f"memo: {timeit.timeit(lambda: fib_memo(n), number=10):.6f} s")
print(f"iter: {timeit.timeit(lambda: fib_iter(n), number=10):.6f} s")Типичные результаты: naive около 3 секунд, memo около 0.0001 секунды, iter около 0.00005 секунды. Итеративная версия немного быстрее мемоизованной из-за отсутствия overhead на dict-lookup, но обе на много порядков быстрее наивной.
Попробуй сам
Реализуйте рекурсивный обход списка и сумму его элементов:
def sum_recursive(xs, i=0):
"""Сумма xs, начиная с индекса i."""
# base case: дошли до конца
if i == len(xs):
return 0
# recursive step: текущий + сумма остальных
return xs[i] + sum_recursive(xs, i + 1)
print(sum_recursive([1, 2, 3, 4, 5])) # 15Сравните глубину рекурсии с длиной списка. Попробуйте sum_recursive(list(range(1000))) — это работает. А list(range(10000)) — RecursionError, потому что лимит стека по умолчанию 1000. Об этом — в следующих уроках.