# Рекурсия

> Приём, при котором функция вызывает саму себя для подзадачи меньшего размера; основа обхода деревьев, алгоритмов «разделяй и властвуй» и динамического программирования.

Источник: https://llmdocs.ru/wiki/recursion/ · обновлено 2026-11-09 · лицензия CC BY-SA 4.0

- **Составные части**: базовый случай + рекурсивный шаг
- **Механизм**: стек вызовов
- **Риски**: переполнение стека, экспоненциальные повторные вычисления
- **Лимит Python**: ~1000 уровней (sys.getrecursionlimit)
- **Оптимизация**: хвостовые вызовы (Scheme, Haskell; не в Python, Java, Go)
- **Связанное**: мемоизация, динамическое программирование
**Рекурсия** — приём, при котором функция решает задачу, вызывая саму себя для одной или нескольких меньших копий той же задачи. Многие структуры по своей природе рекурсивны: каталог содержит каталоги, дерево — поддеревья, выражение — подвыражения, JSON-объект — вложенные объекты. Для них рекурсивное решение получается коротким и прямо повторяет определение данных. Рекурсия лежит в основе алгоритмов «разделяй и властвуй», таких как [сортировка слиянием](https://llmdocs.ru/wiki/sorting.md), обхода [деревьев и графов](https://llmdocs.ru/wiki/trees-graphs.md) и динамического программирования.

## Устройство

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

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

```python
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 ГБ).

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

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

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

```python
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 официально её не гарантирует.

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

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

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

`fib(40)` выполняет сотни миллионов вызовов. Решение — **мемоизация**: запоминать результаты уже решённых подзадач, например в [хеш-таблице](https://llmdocs.ru/wiki/hash-table.md).

```python
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-нотация](https://llmdocs.ru/wiki/big-o.md)).

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

- **Обход деревьев**: файловой системы, DOM, синтаксического дерева в [компиляторе](https://llmdocs.ru/wiki/compiler-interpreter.md), вложенного [JSON](https://llmdocs.ru/wiki/json.md).
- **Поиск в глубину** по графу, перебор с возвратом (backtracking): судоку, расстановка ферзей, генерация перестановок.
- **Разделяй и властвуй**: сортировки, быстрое умножение, построение кучи.
- **Рекурсивный спуск** — разбор выражений и языков программирования.

```python
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-нотация](https://llmdocs.ru/wiki/big-o.md)
- [Сортировка](https://llmdocs.ru/wiki/sorting.md)
- [Дерево и граф](https://llmdocs.ru/wiki/trees-graphs.md)
- [Структуры данных](https://llmdocs.ru/wiki/data-structures.md)

## Источники

1. [Abelson, Sussman — Structure and Interpretation of Computer Programs, 1.2](https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/6515/sicp.zip/full-text/book/book-Z-H-11.html)
2. [Python Docs — sys.setrecursionlimit](https://docs.python.org/3/library/sys.html#sys.setrecursionlimit)
3. [Python Docs — functools.cache](https://docs.python.org/3/library/functools.html#functools.cache)
4. [Cormen et al. — Introduction to Algorithms, ch. 4 (Divide-and-Conquer)](https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/)
5. [Guido van Rossum — Tail Recursion Elimination (2009)](https://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html)