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

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

Базовый случай и рекурсивный шаг

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

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

Посмотрим на простой пример без конкретной реализации. Допустим, задача — обработать натуральное число n. Тогда структура выглядит так:

def f(n):
    if n == 0:          # базовый случай
        return 0
    return 1 + f(n - 1) # рекурсивный шаг: n уменьшается на 1

Ключевое слово здесь — строго. Аргумент рекурсивного шага должен быть ближе к базовому случаю, чем текущий. Если n уменьшается на 1 при каждом вызове и база — n == 0, то цепочка вызовов конечна: за ровно n шагов мы её достигнем.

Что будет, если база есть, но аргумент не приближается к ней? Например:

def broken(n):
    if n == 0:
        return 0
    return broken(n)   # передаём тот же n — бесконечный цикл

Python в этом случае не будет выполнять вызовы бесконечно: при достижении настроенного предела глубины он выбросит RecursionError. Текущее значение предела можно узнать через sys.getrecursionlimit(). Но суть ошибки не техническая, а логическая: рекурсивный шаг не сужает задачу.

А что, если базового случая нет вовсе?

def also_broken(n):
    return also_broken(n - 1)   # n → -∞, остановки нет

Тот же RecursionError, другая причина: нет условия выхода.

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

Стек вызовов и ручная трассировка

Когда одна функция вызывает другую, Python сохраняет текущее состояние выполнения — локальные переменные, аргументы, адрес точки возврата — в структуре, которая называется фреймом. Фреймы складываются в стек: каждый новый вызов кладёт фрейм сверху, каждый возврат снимает его.

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

Как трассировать вручную. Возьмём абстрактную функцию f(n), которая вызывает f(n-1). Трассировка состоит из двух фаз.

Спуск — фиксируем вызовы по порядку:

f(4) вызывает f(3)
f(3) вызывает f(2)
f(2) вызывает f(1)
f(1) вызывает f(0)
f(0) → база, возвращает результат

Подъём — фиксируем возвраты в обратном порядке:

f(0) вернул r0
f(1) получил r0, вернул r1
f(2) получил r1, вернул r2
f(3) получил r2, вернул r3
f(4) получил r3, вернул r4

В пике стека одновременно активны фреймы f(4), f(3), f(2), f(1), f(0) — пять фреймов для n = 4. В общем случае для f(n) одновременно живут n + 1 фрейм.

Для этой абстрактной f(n) каждый фрейм хранит константный объём локального состояния, а максимальная глубина равна n + 1. Поэтому память стека равна Θ(n). В общем случае одного подсчёта фреймов недостаточно: фрейм может удерживать объект переменного размера, и такую память нужно учитывать отдельно.

Важно не путать глубину стека с количеством всех вызовов. Вызовов тоже n + 1, но они идут последовательно: в каждый момент в стеке присутствуют только ещё не завершившиеся фреймы. Для линейной рекурсии это все вызовы сразу — они вложены один в другой. Именно поэтому глубина и суммарное число вызовов совпадают.

Это свойство — одновременная жизнь фреймов — и есть причина, по которой пространственная сложность рекурсии ненулевая даже у функций, которые «просто считают число».

Рекурсивный факториал и сумма списка: реализация и анализ сложности

Факториал — классический первый пример, и это не случайно: его структура буквально совпадает с шаблоном из предыдущей секции.

def factorial(n: int) -> int:
    if n < 0:
        raise ValueError("factorial определён только для n >= 0")
    if n == 0:          # база: 0! = 1
        return 1
    return n * factorial(n - 1)  # шаг: n! = n · (n-1)!

Трассировка для factorial(4):

Спуск:
  factorial(4) → 4 * factorial(3)
  factorial(3) → 3 * factorial(2)
  factorial(2) → 2 * factorial(1)
  factorial(1) → 1 * factorial(0)
  factorial(0) → 1

Подъём:
  factorial(0) = 1
  factorial(1) = 1 * 1 = 1
  factorial(2) = 2 * 1 = 2
  factorial(3) = 3 * 2 = 6
  factorial(4) = 4 * 6 = 24

В пике стека живут 5 фреймов. В модели, где одно умножение считается элементарной операцией, выполняется Θ(n) умножений; глубина и память стека равны Θ(n). Реальное время умножения больших целых зависит от числа цифр, поэтому эта оценка относится к числу шагов рекурсии.

---

Теперь сумма списка — и здесь скрыта нетривиальная ловушка.

def sum_list_slice(lst: list) -> int:
    if not lst:           # база: пустой список
        return 0
    return lst[0] + sum_list_slice(lst[1:])  # срез создаёт новый список

Выглядит аккуратно, но lst[1:] — это не указатель на хвост, это копия хвоста. На уровне рекурсии k живёт срез длины n - k. Пока рекурсия идёт вниз, все эти срезы находятся в памяти одновременно:

Уровень 0: lst длиной n  (оригинал, хранится снаружи)
Уровень 1: срез длиной n-1
Уровень 2: срез длиной n-2
...
Уровень n-1: срез длиной 1
Уровень n: пустой список

Суммарная память срезов: (n-1) + (n-2) + … + 1 + 0 = n(n-1)/2 = Θ(n²). Время копирования — тоже Θ(n²), потому что каждый срез создаётся за время, пропорциональное его длине. Глубина стека при этом остаётся Θ(n), но общая пространственная сложность определяется квадратичными срезами.

Исправление простое: передавать индекс вместо среза.

def sum_list(lst: list, i: int = 0) -> int:
    if i == len(lst):       # база: индекс вышел за конец
        return 0
    return lst[i] + sum_list(lst, i + 1)  # шаг: i строго растёт

Здесь никаких копий нет. Все фреймы держат только целое число i и ссылку на один и тот же список. Время — Θ(n), пространство стека — Θ(n), дополнительная память на данные — O(1).

Проверим согласованность:

assert sum_list([1, 2, 3, 4, 5]) == 15
assert sum_list([]) == 0
assert sum_list_slice([1, 2, 3, 4, 5]) == 15

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

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

У факториала и суммы списка глубина стека растёт линейно — с каждым шагом аргумент уменьшается на 1. Бинарный поиск устроен иначе: на каждом шаге область поиска уменьшается вдвое. Посмотрим, что это даёт стеку.

def binary_search(arr: list, target: int, lo: int, hi: int) -> int:
    """Ищет target в отсортированном arr[lo:hi]. Возвращает индекс или -1."""
    if lo >= hi:                        # база: область пуста
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:              # база: нашли
        return mid
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)   # правая половина
    return binary_search(arr, target, lo, mid)           # левая половина

Вызов: binary_search(arr, target, 0, len(arr)).

Проверка:

arr = [1, 3, 5, 7, 9, 11, 13]
assert binary_search(arr, 7, 0, len(arr)) == 3
assert binary_search(arr, 6, 0, len(arr)) == -1
assert binary_search(arr, 1, 0, len(arr)) == 0
assert binary_search(arr, 13, 0, len(arr)) == 6

Почему глубина O(log n). Инвариант: каждый рекурсивный вызов получает область [lo, hi) с размером hi - lo. После вычисления mid один из двух вызовов получит область размером не более ⌊(hi - lo) / 2⌋. Значит, размер уменьшается как минимум вдвое на каждом уровне:

Уровень 0: область размером n
Уровень 1: область ≤ n/2
Уровень 2: область ≤ n/4
...
Уровень k: область ≤ n/2ᵏ

После k делений размер области не превосходит ⌊n / 2ᵏ⌋. Если считать и завершающий вызов с пустой областью, для n >= 1 максимальное число одновременных фреймов не превосходит ⌊log₂ n⌋ + 2; для пустого массива это один фрейм. Асимптотически глубина равна O(log n).

Для массива из 1 000 000 элементов линейная рекурсия (как у factorial) потребовала бы около миллиона одновременных фреймов. Неуспешный бинарный поиск использует не более 21 фрейма. Это и есть практическая ценность логарифмической глубины: пространственная сложность по стеку — O(log n) вместо O(n).

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

Сравнение итогов:

Алгоритм	Глубина стека	Память стека
factorial(n)	n + 1	Θ(n)
sum_list с индексом	n + 1	Θ(n)
binary_search	≤ ⌊log₂ n⌋ + 2 при n ≥ 1	O(log n)