call stack

A call stack is a stack data structure that tracks the function calls active in a running program, recording where each call should resume once the routine it invoked returns. It follows last-in, first-out (LIFO) order, so the most recently called function is always the first to finish and be removed. The structure also goes by the names execution stack, control stack, and run-time stack.

Each active call is represented by a stack frame, sometimes called an activation record, which the program pushes onto the stack when the call begins and pops off when the call returns. A single frame bundles the state that one invocation needs:

• The arguments passed into the call.
• The local variables that exist only for the duration of the call.
• The return address, which marks the instruction where execution resumes in the caller.

The figure below steps through a short program in which each call pushes a frame onto the stack and each return pops one off, with every frame showing its arguments, local variables, and return address.

The stack grows taller with each nested call and shrinks as calls return, so a long chain of nested or recursive calls makes it deep. If the calls never stop returning, as with unbounded recursion, the stack can exhaust its reserved memory and trigger a stack overflow, which usually crashes the program.

Python guards against this with a configurable recursion limit, raising a RecursionError before the interpreter’s underlying stack overflows. A traceback then reports the frames that were still on the stack at the moment an exception was raised.

Related Resources

Tutorial

Thinking Recursively in Python

Learn how to work with recursion in your Python programs by mastering concepts such as recursive functions and recursive data structures.

intermediate python

For additional information on related topics, take a look at the following resources:

• Recursion in Python: An Introduction (Tutorial)
• Understanding the Python Traceback (Tutorial)
• Getting the Most Out of a Python Traceback (Course)
• Stacks and Queues: Selecting the Ideal Data Structure (Course)
• Recursion in Python (Course)
• Thinking Recursively With Python (Course)
• Recursion in Python: An Introduction (Quiz)
• Understanding the Python Traceback (Quiz)