Что такое call stack

Когда программа вызывает функцию, процессор должен запомнить, куда вернуться после её выполнения. Для этого существует call stack — структура данных в памяти процесса, работающая как LIFO-стек.

Каждый вызов функции добавляет на стек stack frame — блок данных, содержащий:

1. Адрес возврата (куда продолжить после return).
2. Локальные переменные функции.
3. Аргументы функции.
4. Сохранённые регистры (если функция их меняет).

Когда функция возвращается — её frame удаляется со стека, и выполнение продолжается с адреса возврата.

Когда factorial(0) возвращает 1, его frame удаляется. Теперь factorial(1) может вычислить 1 * 1 = 1 и тоже завершиться, удалив свой frame. И так далее, пока стек не вернётся к main.

Stack frame в CPython

В CPython stack frame — это не просто адрес возврата и пара переменных. Это полноценный объект PyFrameObject, который содержит:

• f_locals — словарь локальных переменных функции.
• f_globals — ссылка на словарь модуля.
• f_code — объект кода (PyCodeObject) с bytecode функции.
• f_lasti — индекс последней выполненной инструкции bytecode.
• f_back — указатель на предыдущий frame.
• value stack — стек значений для bytecode (промежуточные значения).
• block stack — стек для управления циклами и try/except.
• exception state — если внутри обработки исключения.

Это много данных. Один Python frame занимает 400-600 байт. Сравните с C, где stack frame может быть 16-32 байта. Поэтому в Python рекурсия на 100 000 уровней — это 50+ МБ только на стек.

import sys

def show_frame():
    frame = sys._getframe()
    print(f"locals: {frame.f_locals}")
    print(f"code:   {frame.f_code.co_name}")
    print(f"line:   {frame.f_lineno}")

show_frame()

Если запустить, увидите словарь локальных переменных, имя функции и текущую строку. Это и есть содержимое frame, к которому можно обратиться напрямую.

Глубина рекурсии и sys.setrecursionlimit

Стек — конечный. Если его исчерпать, программа упадёт. В Python для этого предусмотрена защита: проверка глубины рекурсии. По умолчанию лимит — 1000 уровней:

import sys
print(sys.getrecursionlimit())   # 1000

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

deep_recursion(999)    # ok
deep_recursion(1000)   # RecursionError

При превышении лимита Python бросает RecursionError. Это искусственное ограничение, ставящееся ДО реального переполнения стека ОС.

Зачем оно? Чтобы избежать настоящего segfault (необработанное обращение к памяти за пределами стека). С искусственным лимитом вы получаете аккуратное исключение и можете его обработать.

Лимит можно поднять:

sys.setrecursionlimit(10_000)
deep_recursion(9000)   # теперь ok

Но это рискованно: реальный размер OS-стека обычно 1-8 МБ, и при ~500 байт на frame это позволяет 2000-16000 frames. Поднять лимит до 100 000 — это путь к segfault без возможности обработки. CPython при этом просто умрёт.

Реальный лимит стека ОС

Размер стека на потоке определяется операционной системой. Обычно:

• Linux: 8 МБ по умолчанию (ulimit -s).
• macOS: 8 МБ.
• Windows: 1 МБ.

Это лимит на каждый поток, не на процесс. У main-thread обычно 8 МБ, у дополнительных потоков, созданных через threading.Thread, — меньше (1 МБ по умолчанию). Это причина странных сценариев: «работает в main, падает в потоке».

Поднять лимит ОС можно через ulimit -s unlimited (Linux/macOS) или явный threading.stack_size() для конкретного потока:

import threading
threading.stack_size(16 * 1024 * 1024)   # 16 МБ на новые потоки

def worker():
    # тут можно более глубокую рекурсию
    pass

t = threading.Thread(target=worker)
t.start()

Но это уже edge case. В нормальной разработке мы стараемся не делать глубоких рекурсий.

Что весит больше: глубина или ветвление

Иногда забывают: рекурсия может быть глубокой, но узкой (один вызов на уровень), или мелкой, но широкой (много вызовов на уровень).

Глубокая узкая рекурсия (factorial, sum_list) — глубина n, ширина 1. Stack frames в каждый момент времени: n. Это упирается в лимит стека.

Широкая мелкая рекурсия (двоичное дерево обхода) — глубина log(n), ширина 2 на уровень. Stack frames: log(n). Это безопасно.

Глубокая широкая (naive fib) — глубина n, ширина 2 на уровень. Frames одновременно: n (потому что мы спускаемся в один путь до конца, а другой ждёт). Но общее число вызовов за всё время — экспоненциально.

Это важно: stack frames в моменте — это не общее число вызовов, а глубина в данный момент. Так что Фибоначчи не падает из-за глубины (она линейна), а падает из-за времени (экспоненциальное число вызовов).

Tail call в CPython: его нет

В некоторых языках (Scheme, Scala, Haskell) есть tail call optimization (TCO). Если рекурсивный вызов — последняя операция функции, компилятор не создаёт новый frame, а переиспользует текущий. Глубина рекурсии становится константной.

В Python TCO умышленно отсутствует. Гвидо ван Россум писал об этом несколько раз: TCO ухудшает читаемость traceback’ов (теряется цепочка вызовов в debug), а Python ценит readability и debugging. О подробностях tail recursion — следующий урок.

Замеры памяти

Посчитаем, сколько памяти занимают frames в Python:

import sys
import tracemalloc

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

tracemalloc.start()
deep(900)   # глубина 900
snapshot = tracemalloc.take_snapshot()
total = sum(stat.size for stat in snapshot.statistics('filename'))
print(f"total tracked: {total / 1024:.1f} KB")
tracemalloc.stop()

Точные цифры зависят от версии Python, но порядок: глубина 1000 ~ 500-700 КБ только на frames. Это не много, пока вы не делаете рекурсию на миллионе элементов.

Попробуй сам

Поиграйте с лимитами:

import sys

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

# по умолчанию
try:
    recursive_count(1100)
except RecursionError as e:
    print(f"при лимите {sys.getrecursionlimit()}: {e}")

# поднимем лимит
sys.setrecursionlimit(5000)
try:
    print(f"recursive_count(4000) = {recursive_count(4000)}")
except RecursionError as e:
    print(f"при лимите 5000: {e}")

# слишком высоко — segfault реален
sys.setrecursionlimit(1_000_000)
try:
    recursive_count(900_000)   # может упасть segfault'ом
except RecursionError as e:
    print(f"при лимите 10^6: {e}")

Запускайте по очереди — последний может убить интерпретатор без возможности обработать. Лучше не запускать на проде.