Рекурсия

Рекурсия - это когда функция вызывает саму себя. Сильный инструмент для задач с вложенной структурой: деревья, вложенные словари, файловые системы.

Аналогичная тема есть в Go и PHP - Python-специфика здесь: лимит стека sys.setrecursionlimit, мемоизация через @lru_cache и встроенный Path.rglob.

Основы

Каждая рекурсивная функция должна иметь:

1. Базовый случай - когда рекурсия останавливается
2. Рекурсивный шаг - вызов себя с уменьшенной задачей

def factorial(n: int) -> int:
    if n <= 1:          # базовый случай
        return 1
    return n * factorial(n - 1)  # рекурсивный шаг

print(factorial(5))  # 120

Что происходит в памяти

factorial(5)
  -> 5 * factorial(4)
    -> 4 * factorial(3)
      -> 3 * factorial(2)
        -> 2 * factorial(1)
          -> 1  <- базовый случай
        <- 2 * 1 = 2
      <- 3 * 2 = 6
    <- 4 * 6 = 24
  <- 5 * 24 = 120

Каждый вызов создаёт фрейм в стеке. Python хранит в нём локальные переменные, ссылку на вызывающий фрейм и текущую инструкцию.

Лимит стека в Python

import sys

print(sys.getrecursionlimit())  # 1000

# Поднять лимит (осторожно - можно исчерпать память стека)
sys.setrecursionlimit(5000)

Для глубоких структур лучше переписать итеративно с явным стеком или использовать встроенные итераторы.

Примеры

Числа Фибоначчи

# Наивная реализация - O(2^n), экспоненциально медленно
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

fib(40) делает ~330 миллионов вызовов. С @lru_cache из functools - один проход:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(100))  # мгновенно

В Python 3.9+ есть @functools.cache - то же самое, но короче:

from functools import cache

@cache
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

@lru_cache и @cache - декораторы, которые прозрачно кэшируют результаты по аргументам.

Обход вложенного словаря

def flatten_dict(d: dict, prefix: str = '') -> dict:
    result = {}
    for key, value in d.items():
        full_key = f'{prefix}.{key}' if prefix else key
        if isinstance(value, dict):
            result.update(flatten_dict(value, full_key))  # рекурсия
        else:
            result[full_key] = value
    return result

config = {'db': {'host': 'localhost', 'port': 5432}, 'debug': True}
print(flatten_dict(config))
# {'db.host': 'localhost', 'db.port': 5432, 'debug': True}

Обход файловой системы

import os

def list_files(path: str, indent: int = 0) -> None:
    prefix = '  ' * indent
    for entry in os.scandir(path):
        print(f'{prefix}{entry.name}')
        if entry.is_dir():
            list_files(entry.path, indent + 1)  # рекурсия

list_files('.')

Python предоставляет Path.rglob() - итеративный обход без ограничения стека:

from pathlib import Path

# Все .py файлы рекурсивно - без RecursionError на любой глубине
for path in Path('.').rglob('*.py'):
    print(path)

Подробнее о pathlib - в уроке stdlib-os-pathlib.

Бинарный поиск (рекурсивный)

def binary_search(arr: list[int], target: int, lo: int, hi: int) -> int:
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)
    return binary_search(arr, target, lo, mid - 1)

nums = [1, 3, 5, 7, 9, 11]
print(binary_search(nums, 7, 0, len(nums) - 1))  # 3

Рекурсия vs Итерация

# Рекурсия
def factorial_rec(n: int) -> int:
    if n <= 1:
        return 1
    return n * factorial_rec(n - 1)

# Итерация - не использует стек, нет риска RecursionError
def factorial_iter(n: int) -> int:
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

<ComparisonTable data={{ headers: ["", "Рекурсия", "Итерация"], rows: [ ["Читаемость", "Для деревьев, графов - понятнее", "Для линейных задач - проще"], ["Память", "O(n) фреймов стека", "O(1)"], ["Лимит Python", "1000 по умолчанию", "Нет ограничений"], ["Мемоизация", "@lru_cache одной строкой", "Вручную через dict"], ["Когда", "Деревья, вложенные структуры, графы", "Массивы, числа, линейные задачи"] ] }} />

Типичные ошибки

# ОШИБКА 1: нет базового случая
def infinite(n: int) -> int:
    return n + infinite(n - 1)  # RecursionError через ~1000 вызовов

# ОШИБКА 2: базовый случай недостижим
def bad_fib(n: int) -> int:
    if n == 0:
        return 0
    return bad_fib(n - 1) + bad_fib(n - 2)  # при n=1 уйдёт в bad_fib(-1)

# ОШИБКА 3: наивная рекурсия без кэша для перекрывающихся подзадач
fib(50)  # работает годами без @lru_cache

# ОШИБКА 4: lambda не может быть рекурсивной
# fact = lambda n: 1 if n <= 1 else n * fact(n - 1)  # NameError при вызове
# Правильно: def fact(n): ...

Мини-практика

1. Напиши sum_nested(data: list) -> int - сумма всех чисел в произвольно вложенном списке
2. Напиши count_files(path: str) -> int - количество файлов в дереве каталогов (рекурсивно)
3. Реши ту же задачу через Path.rglob - без рекурсии
4. Добавь @lru_cache к наивному fib и замерь разницу через timeit