Рекурсия

Идея рекурсии

Рекурсивная функция решает задачу, сводя её к такой же задаче меньшего размера. Ей нужны две части:

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

def countdown(n):
    if n == 0:                 # базовый случай
        print("Пуск!")
        return
    print(n)
    countdown(n - 1)           # рекурсивный шаг

countdown(3)

Стек вызовов

Каждый вызов функции получает свой кадр (frame) — со своими локальными переменными. Кадры складываются в стек:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(4))

Нажмите 👣 Пошагово и следите за колонкой кадров: при спуске появляются factorial() с n = 4, 3, 2, 1, а при возврате кадры снимаются, и результаты перемножаются.

Лимит глубины

CPython ограничивает глубину рекурсии (по умолчанию около 1000), чтобы не переполнить стек процесса:

import sys
print(sys.getrecursionlimit())

def depth(n):
    return depth(n + 1)

try:
    depth(0)
except RecursionError as e:
    print("RecursionError:", e)

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

Рекурсия или цикл

def sum_rec(nums):
    if not nums:
        return 0
    return nums[0] + sum_rec(nums[1:])     # каждый срез — копия: O(n²) времени и памяти

def sum_loop(nums):
    total = 0
    for x in nums:
        total += x
    return total

print(sum_rec([1, 2, 3, 4]), sum_loop([1, 2, 3, 4]))

Рекурсия естественна для рекурсивных структур: деревья, вложенные списки и словари, файловая система, грамматики; и для алгоритмов «разделяй и властвуй»: сортировка слиянием, быстрая сортировка, бинарный поиск, перебор с возвратом. Для линейных задач цикл проще и быстрее.

Вложенные структуры

config = {
    "db": {"host": "localhost", "port": 5432},
    "cache": {"redis": {"host": "r1", "ttl": 60}},
    "debug": True,
}

def walk(d, prefix=""):
    for key, value in d.items():
        path = f"{prefix}.{key}" if prefix else key
        if isinstance(value, dict):
            walk(value, path)              # спускаемся глубже
        else:
            print(f"{path} = {value}")

walk(config)

Дерево

tree = {"value": 1, "children": [
    {"value": 2, "children": [{"value": 4, "children": []}]},
    {"value": 3, "children": []},
]}

def tree_sum(node):
    return node["value"] + sum(tree_sum(child) for child in node["children"])

def tree_depth(node):
    if not node["children"]:
        return 1
    return 1 + max(tree_depth(c) for c in node["children"])

print(tree_sum(tree), tree_depth(tree))

Мемоизация

Наивная рекурсия для чисел Фибоначчи пересчитывает одно и то же экспоненциально много раз. Кеш превращает её в линейную:

from functools import cache

calls = 0
def fib(n):
    global calls
    calls += 1
    return n if n < 2 else fib(n - 1) + fib(n - 2)

fib(20)
print("вызовов без кеша:", calls)

@cache
def fib_fast(n):
    return n if n < 2 else fib_fast(n - 1) + fib_fast(n - 2)

print(fib_fast(100))

Это первый шаг к динамическому программированию (урок в модуле алгоритмов).

Как придумать рекурсивное решение

1. Сформулируйте, что возвращает функция для входа размера n.
2. Найдите самый простой вход (пустой список, 0, лист дерева) — базовый случай.
3. Предположите, что функция уже работает для меньшего входа («доверьтесь рекурсии»), и выразите ответ для n через ответ для меньшего.
4. Убедитесь, что каждый вызов приближает к базовому случаю.

Итог

• Рекурсия = базовый случай + шаг к меньшей задаче.
• Каждый вызов — новый кадр стека; лимит ~1000, иначе RecursionError; TCO в CPython нет.
• Рекурсия хороша для деревьев, вложенных структур и «разделяй и властвуй»; для линейных задач — цикл.
• Повторные вычисления убирает мемоизация (@cache).