Рекурсия

Рекурсия — приём, при котором функция решает задачу, вызывая саму себя для одной или нескольких меньших копий той же задачи. Многие структуры по своей природе рекурсивны: каталог содержит каталоги, дерево — поддеревья, выражение — подвыражения, JSON-объект — вложенные объекты. Для них рекурсивное решение получается коротким и прямо повторяет определение данных. Рекурсия лежит в основе алгоритмов «разделяй и властвуй», таких как сортировка слиянием, обхода деревьев и графов и динамического программирования.

Устройство

Корректная рекурсивная функция состоит из двух частей:

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

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

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

Стек вызовов

Каждый вызов функции получает кадр стека с локальными переменными и адресом возврата. При рекурсии кадры накапливаются: factorial(1000) держит в памяти тысячу кадров одновременно. Размер стека ограничен, и слишком глубокая рекурсия приводит к переполнению стека: в Python — RecursionError (лимит по умолчанию около 1000 уровней),^[2] в C — аварийное завершение, в Go стеки горутин растут динамически, но тоже имеют предел (по умолчанию 1 ГБ).

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

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

Вызов называется хвостовым, если это последнее действие функции и его результат сразу возвращается:

def factorial_acc(n, acc=1):
    if n <= 1:
        return acc
    return factorial_acc(n - 1, acc * n)   # хвостовой вызов

Компилятор может заменить такой вызов переходом, не создавая новый кадр, — это оптимизация хвостовых вызовов (TCO). Её гарантируют Scheme и многие функциональные языки, а Haskell, OCaml, Scala (@tailrec) и компиляторы C/C++ на высоких уровнях оптимизации применяют её на практике.^[1] Python, Java и Go её не делают: Гвидо ван Россум сознательно отказался от неё ради понятных трассировок стека.^[5] Rust официально её не гарантирует.

Ловушка повторных вычислений

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

def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)   # O(φⁿ) ≈ O(1.6ⁿ)

fib(40) выполняет сотни миллионов вызовов. Решение — мемоизация: запоминать результаты уже решённых подзадач, например в хеш-таблице.

from functools import cache

@cache
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)   # O(n)

Декоратор functools.cache делает это одной строкой.^[3] Мемоизация рекурсивного решения — это динамическое программирование «сверху вниз»; тот же алгоритм можно записать «снизу вверх» циклом с таблицей, избавившись и от глубокой рекурсии.

Сложность

Время рекурсивного алгоритма описывают рекуррентным соотношением. Для сортировки слиянием T(n) = 2T(n/2) + O(n): две половины плюс линейное слияние. Основная теорема (master theorem) даёт ответ O(n log n).^[4] Двоичный поиск: T(n) = T(n/2) + O(1) → O(log n). Дополнительная память рекурсии равна максимальной глубине стека — это нужно учитывать в оценке (см. Алгоритм и O-нотация).

Типичные применения

• Обход деревьев: файловой системы, DOM, синтаксического дерева в компиляторе, вложенного JSON.
• Поиск в глубину по графу, перебор с возвратом (backtracking): судоку, расстановка ферзей, генерация перестановок.
• Разделяй и властвуй: сортировки, быстрое умножение, построение кучи.
• Рекурсивный спуск — разбор выражений и языков программирования.

from pathlib import Path

def total_size(path: Path) -> int:
    if path.is_file():
        return path.stat().st_size
    return sum(total_size(p) for p in path.iterdir())

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

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

См. также

• Алгоритм и O-нотация
• Сортировка
• Дерево и граф
• Структуры данных

Источники

1. Abelson, Sussman — Structure and Interpretation of Computer Programs, 1.2
2. Python Docs — sys.setrecursionlimit
3. Python Docs — functools.cache
4. Cormen et al. — Introduction to Algorithms, ch. 4 (Divide-and-Conquer)
5. Guido van Rossum — Tail Recursion Elimination (2009)