Как работает стек вызовов в Python: разбор на трёх простых функциях

Что такое кадр функции

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

Удобная бытовая аналогия — стопка подносов в столовой. Новый поднос кладут сверху, а берут тоже сверху, поэтому поднос, положенный первым, окажется на дне и будет взят последним. Кадр функции ведёт себя точно так же: функция, вызванная первой, вернётся последней, потому что её кадр лежит в самом низу стопки.

Три вложенные функции на практике

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

Порядок возврата подчиняется простому правилу

Функция third завершается первой и возвращает своё значение в то самое место внутри second, откуда её позвали, а её кадр сразу снимается со стека. Дальше выполнение продолжается внутри second с того места, где остановилось, second доходит до своего return и тоже возвращается — в first, а её кадр снимается следующим. Последним завершается first и передаёт результат туда, откуда была вызвана сама программа. Порядок возврата всегда зеркален порядку вызова: кто позвал последним, тот и вернётся первым.

Почему это правило нельзя нарушить

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

Рекурсия и переполнение стека

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

Python по умолчанию ограничивает глубину рекурсии примерно тысячью вложенных вызовов через модуль sys и функцию setrecursionlimit, и при достижении этого предела интерпретатор поднимает исключение RecursionError вместо того, чтобы дать программе упасть без объяснений. Лимит существует не ради красоты — реальная память под стек конечна, и без искусственного потолка бесконечная рекурсия рано или поздно исчерпала бы её целиком и завершила программу куда менее аккуратной ошибкой.

• аргументы функции хранятся в её собственном кадре, а не где-то ещё
• локальные переменные функции живут ровно столько же, сколько её кадр
• адрес точки возврата хранится в кадре ВЫЗЫВАЮЩЕЙ функции
• снять можно только верхний кадр стека, произвольный доступ невозможен

Как читать traceback снизу вверх

Когда исключение долетает до верхнего уровня программы, Python печатает traceback — список всех кадров, которые были в стеке на момент ошибки, от самого первого вызова до самого последнего. Заголовок над списком прямо говорит most recent call last, то есть самый недавний вызов идёт последним в выводе — и это ключ к чтению всего блока. Верхняя строка traceback описывает самый первый вызов в цепочке, обычно строку запуска программы, а нижняя строка — тот кадр, в котором исключение реально возникло.

На примере трёх функций из этой статьи ошибка внутри third даст traceback из четырёх блоков подряд: сверху вызов first в основном коде программы, следом строка внутри first, где вызывается second, затем строка внутри second, где вызывается third, и в самом низу — та строка внутри third, где именно произошло деление на ноль, вместе с текстом самого исключения. Читать это стоит с конца: последняя строка называет тип ошибки и место, где она произошла, а строки выше по порядку показывают, через какую цепочку вызовов программа до этого места дошла.