Рекурсия: как работает и когда применять

Устройство рекурсивного вызова, база и шаг рекурсии, стек вызовов и переполнение, мемоизация, хвостовая рекурсия и перевод в цикл, разбор классических задач.

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

Два обязательных элемента

def factorial(n):
    if n <= 1:          # база рекурсии — условие остановки
        return 1
    return n * factorial(n - 1)   # шаг — вызов для меньшего аргумента

# factorial(4)
#   → 4 * factorial(3)
#       → 3 * factorial(2)
#           → 2 * factorial(1)
#               → 1          база достигнута
#           ← 2
#       ← 6
#   ← 24

Стек вызовов

Каждый вызов кладёт в стек кадр: аргументы, локальные переменные и адрес возврата. Кадры снимаются в обратном порядке. Глубина стека ограничена: в Python по умолчанию около 1000 вызовов, в C++ ограничение задаётся размером стека потока, обычно 1-8 МБ.

import sys
print(sys.getrecursionlimit())   # 1000
sys.setrecursionlimit(10000)     # менять осторожно: может упасть интерпретатор

Классические задачи

# Числа Фибоначчи — наивно
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)
# fib(40) считается несколько секунд: O(2ⁿ) вызовов

# Обход дерева
def tree_sum(node):
    if node is None:
        return 0
    return node.value + tree_sum(node.left) + tree_sum(node.right)

# Быстрая сортировка
def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = a[len(a) // 2]
    less    = [x for x in a if x < pivot]
    equal   = [x for x in a if x == pivot]
    greater = [x for x in a if x > pivot]
    return quicksort(less) + equal + quicksort(greater)

# Ханойские башни
def hanoi(n, src, dst, tmp):
    if n == 0:
        return
    hanoi(n - 1, src, tmp, dst)
    print(f'{src} → {dst}')
    hanoi(n - 1, tmp, dst, src)

Мемоизация

Наивный fib пересчитывает одни и те же значения экспоненциальное число раз. Кэширование результатов сводит сложность к линейной — это тот случай, когда одна строка ускоряет программу в миллионы раз.

from functools import lru_cache

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

# fib(100) теперь вычисляется мгновенно
# было O(2ⁿ), стало O(n)

Хвостовая рекурсия

# Не хвостовая: после вызова выполняется умножение
def fact(n):
    return 1 if n <= 1 else n * fact(n - 1)

# Хвостовая: вызов — последнее действие
def fact_tail(n, acc=1):
    return acc if n <= 1 else fact_tail(n - 1, acc * n)

# Итеративный эквивалент — то, во что компилятор превратил бы хвостовой вызов
def fact_iter(n):
    acc = 1
    for i in range(2, n + 1):
        acc *= i
    return acc

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

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

Перебор с возвратом

def permutations(items, current=None, result=None):
    current = current or []
    result  = result if result is not None else []
    if not items:
        result.append(current[:])
        return result
    for i, item in enumerate(items):
        current.append(item)
        permutations(items[:i] + items[i+1:], current, result)
        current.pop()          # шаг назад — суть backtracking
    return result

print(permutations([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

На этой схеме решают задачи о восьми ферзях, судоку, поиск пути в лабиринте — типовые темы курсовых по алгоритмам.