Рекурсия — не только красивая запись, а механизм исполнения: каждый вызов создаёт в стеке вызовов новый фрейм (frame). Поняв стек, вы увидите время, память и причину RecursionError. Этот урок углубляет тему введения в рекурсию со стороны анализа и стека.

Три составляющие

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

Трассировка стека вызовов

В трассировке факториала каждая строка — создание фрейма, а каждая -> — возврат значения и удаление фрейма. Отступ — это глубина: в момент fact(0) в стеке 4 фрейма.

python
def fact(n, depth=0):
    pad = "  " * depth
    print(f"{pad}fact({n})")
    if n == 0:
        print(f"{pad}-> 1")
        return 1
    result = n * fact(n - 1, depth + 1)
    print(f"{pad}-> {result}")
    return result

fact(3)
text
fact(3)
  fact(2)
    fact(1)
      fact(0)
      -> 1
    -> 1
  -> 2
-> 6
Стек вызовов для `fact(3)`: фреймы добавляются при спуске и снимаются при возврате
Стек вызовов для fact(3): фреймы добавляются при спуске и снимаются при возврате

Размер стека и RecursionError

CPython ограничивает глубину вызовов: лимит по умолчанию sys.getrecursionlimit() равен 1000. При превышении возникает RecursionError, который защищает программу от переполнения C-стека и аварийного падения.

python
import sys

def depth(n):
    return 0 if n == 0 else 1 + depth(n - 1)