Рекурсия в программировании: базовый случай, стек вызовов и примеры

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

Ниже разберем, как рекурсия исполняется через стек вызовов, почему она падает с переполнением стека, как ускорить ее мемоизацией и когда лучше взять цикл. Примеры на Python проверены в версиях 3.9 и 3.14.

Сразу мини-словарь, чтобы не путать термины:

Минимальный пример: факториал

Факториал n! = 1 * 2 * … * n удобно определить через себя: 0! = 1, а n! = n * (n-1)!. Код повторяет определение почти дословно:

def factorial(n):
    if n < 0:
        raise ValueError("n must be non-negative")  # отрицательный вход не дойдет до нуля
    if n == 0:          # базовый случай
        return 1
    return n * factorial(n - 1)   # рекурсивный шаг

print(factorial(5))
print(factorial(0))

В консоли появится:

120
1

Строка if n == 0 останавливает рекурсию. Строка return n * factorial(n - 1) уменьшает задачу на единицу, поэтому любой вход n >= 0 рано или поздно дойдет до нуля. Отрицательное n ушло бы в бесконечный спуск мимо нуля, поэтому первая проверка отсекает такой вход сразу: factorial(-1) выбросит ValueError, а не RecursionError через тысячу кадров.

Как это исполняется: стек вызовов

Функция не «повторяется», как цикл. Каждый вызов получает собственный кадр стека со своими переменными, и внешний вызов ждет, пока вернется внутренний. Прогоним factorial(3) руками.

Прямой ход (кадры добавляются в стек):

factorial(3) ждет 3 * factorial(2)
  factorial(2) ждет 2 * factorial(1)
    factorial(1) ждет 1 * factorial(0)
      factorial(0) -> 1          # базовый случай, глубина 4

Обратный ход (кадры снимаются, результаты поднимаются вверх):

factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6

Отсюда главное следствие: пока не выполнен базовый случай, все предыдущие вызовы висят в памяти. Глубина рекурсии для factorial(n) равна n + 1, а память растет линейно от глубины.

Две типичные ошибки

Ошибка 1: нет базового случая.

def countdown(n):
    print(n)
    return countdown(n - 1)   # остановки нет

try:
    countdown(3)
except RecursionError as e:
    print("Ошибка:", type(e).__name__)

Функция печатает 3, 2, 1, 0, -1 и дальше, пока Python не прервет ее. Последняя строка вывода — Ошибка: RecursionError. Текст сообщения зависит от версии Python и от места, где сработал предел, поэтому в коде надежнее ловить тип исключения, а не строку.

Исправление — добавить условие выхода в начало функции:

def countdown(n):
    if n < 0:
        return
    print(n)
    countdown(n - 1)

countdown(3)

Вывод: 3, 2, 1, 0 — по одному числу в строке.

Ошибка 2: шаг не приближает к базовому случаю. Базовый случай есть, но вход его «перепрыгивает»:

def halve_even(n):
    if n == 0:
        return 0
    return halve_even(n - 2)

print(halve_even(4))    # 0
try:
    halve_even(5)       # 5 -> 3 -> 1 -> -1 -> ... мимо нуля
except RecursionError:
    print("RecursionError для n=5")

Для четного n все работает, для нечетного — снова RecursionError. Исправление: условие if n <= 0 вместо n == 0. Общее правило проверки: для любого допустимого входа каждый шаг должен строго приближать аргумент к базовому случаю.

Глубина рекурсии и переполнение стека

Память под стек ограничена, поэтому у рекурсии есть предел глубины. Как он проявляется, зависит от языка:

В Python предел можно поднять через sys.setrecursionlimit(), но это защитный порог, а не размер стека: слишком большой лимит в зависимости от версии и платформы может закончиться аварийным падением интерпретатора вместо понятного исключения. В нашей проверке Python 3.9 на глубине 500 000 упал с SIGSEGV, а Python 3.14 такую же чисто питоновскую рекурсию выдержал. Если нужна глубина в десятки тысяч, надежнее переписать алгоритм на цикл.

Хвостовая рекурсия — случай, когда рекурсивный вызов стоит последним действием функции. Некоторые языки и компиляторы превращают ее в цикл без роста стека: в Scheme это гарантировано стандартом, компиляторы C/C++ часто делают это при оптимизации, но без гарантии. CPython и JVM такую оптимизацию не выполняют, поэтому в Python и Java хвостовая форма от переполнения не спасает.

Где рекурсия естественна: обход дерева

Факториал проще написать циклом. Сила рекурсии — в данных, устроенных рекурсивно: деревья каталогов, вложенный JSON, HTML-документ. Посчитаем суммарный размер вложенных папок:

tree = {
    "docs": {"cv.pdf": 120, "notes.txt": 4},
    "photos": {"2025": {"a.jpg": 800, "b.jpg": 650}, "c.png": 90},
    "todo.txt": 2,
}

def total_size(node):
    if isinstance(node, int):   # базовый случай: файл
        return node
    return sum(total_size(child) for child in node.values())

print(total_size(tree))
print(total_size(tree["photos"]))

Вывод — 1666 и 1540. Глубина вложенности заранее неизвестна: каждая папка передает подпапки тому же коду. Итеративной версии пришлось бы вручную вести стек узлов.

Виды рекурсии

Косвенная рекурсия встречается в парсерах: разбор выражения вызывает разбор слагаемого, а тот снова разбор выражения для скобок.

Мемоизация: когда ветвящаяся рекурсия тормозит

Наивные числа Фибоначчи вычисляют одни и те же значения много раз:

from functools import lru_cache

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

print(fib(30), "вызовов:", calls)

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

print(fib_memo(30), fib_memo.cache_info().misses, "уникальных вычислений")

Вывод:

832040 вызовов: 2692537
832040 31 уникальных вычислений

Мемоизация — кэширование результата функции по аргументам. Она превращает экспоненциальный рост числа вызовов в линейный. Корректна она тогда, когда результат полностью определяется ключом кэша: проще всего это гарантировать для функций, зависящих только от аргументов. У lru_cache аргументы должны быть хешируемыми (список в аргументе даст TypeError); если результат зависит от внешнего состояния — времени, файла, базы, — это состояние нужно включить в ключ или ограничить время жизни кэша. Глубину стека мемоизация не уменьшает: первый вызов fib_memo(5000) при лимите 1000 тоже упадет.

Рекурсия или цикл: как выбрать

Любую рекурсию можно переписать итеративно — циклом или циклом с явным стеком. Вопрос в том, что понятнее и надежнее.

Для сравнения — факториал циклом, без роста стека:

def factorial_loop(n):
    if n < 0:
        raise ValueError("n must be non-negative")  # тот же контракт, что у рекурсивной версии
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_loop(5), len(str(factorial_loop(1000))))

Вывод — 120 2568: в числе 1000! 2568 цифр, а рекурсивная factorial(1000) на нем падает с RecursionError при стандартном лимите. Для чисел длиннее 4300 цифр учтите еще одно ограничение: с Python 3.11 str() для таких int выбрасывает ValueError, предел меняют через sys.set_int_max_str_digits().

Если не получилось

• RecursionError или StackOverflowError сразу — проверьте, есть ли базовый случай и стоит ли он до рекурсивного вызова.
• Ошибка только на части входов — шаг перепрыгивает базовый случай или не обрабатывает отрицательные и пустые значения.
• Ошибка только на больших входах — глубина превышает предел: переходите на цикл или явный стек.
• Результат верный, но очень медленно — ветвящаяся рекурсия пересчитывает подзадачи, нужна мемоизация.
• Неверный результат — прогоните маленький вход руками по стеку, как factorial(3) выше.

Выводы

• Рекурсивная функция = базовый случай + шаг, который строго приближает к нему.
• Каждый вызов занимает кадр стека, поэтому глубина рекурсии ограничена; в CPython лимит интерпретатора по умолчанию 1000, а реально доступная глубина для вашей функции может быть меньше.
• Рекурсия естественна для деревьев и вложенных структур, для простых счетчиков лучше цикл.
• Ветвящуюся рекурсию ускоряет мемоизация, но глубину стека она не уменьшает.
• CPython и JVM не оптимизируют хвостовую рекурсию, так что глубокие вычисления надежнее делать итеративно.

Где применяется / связь с практикой

FAQ

Рекурсия всегда медленнее цикла?
Не всегда. Вызов функции обычно дороже итерации цикла, но для деревьев и «разделяй и властвуй» разница, как правило, мала.

Можно ли просто поставить sys.setrecursionlimit(10 ** 6)?
Технически да, но это снимает защиту: при реальной нехватке стека процесс может упасть аварийно. Для заведомо глубоких входов надежнее итеративное решение.

Чем рекурсия отличается от динамического программирования?
Динамическое программирование — метод решения задач с повторяющимися подзадачами. Его можно реализовать сверху вниз (рекурсия + мемоизация) или снизу вверх (цикл по таблице).