The Call Stack

The Call Stack

Step 1 of 9

frames0order outnewest first

call stack

output

Every call gets a frame: its own arguments, and the line to come back to when the call it made finally returns.

The Idea

Every call gets its own frame holding its arguments and the line to resume on. Frames pile up as the recursion goes deeper, then pop off in reverse as calls return. Stack too deep and Python stops you with a RecursionError.

Real-World Example

Phone calls on hold. You pause your sister to take a work call, then pause that for the courier at the door. The courier clears first, then work, then your sister — the newest interruption is always the first one finished.

The Code

def walk(n, depth=0):
    pad = "  " * depth
    print(pad + "enter " + str(n))   # frame pushed
    if n > 1:
        walk(n - 1, depth + 1)
    print(pad + "leave " + str(n))   # frame about to pop

walk(3)
# enter 3
#   enter 2
#     enter 1
#     leave 1
#   leave 2
# leave 3

Your turn

Put the steps in the right order.

1. 1The walk(1) frame pops and walk(2) resumes↑↓
2. 2The walk(2) frame is pushed↑↓
3. 3The walk(2) frame pops and the stack is empty↑↓
4. 4The walk(1) frame is pushed↑↓

Check order

Mini quiz

1 / 3

In what order do stack frames finish?

• AOldest first
• BNewest first
• CRandom order
• DAlphabetical order