The Call Stack, Visualized: Frames, Tracebacks and Depth

Recursion stops being mysterious the moment you can see the call stack: the pile of unfinished calls, each waiting for the one above it to return. Every program has one, recursive or not. It is what a traceback prints, what limits recursion depth, and the hidden memory cost of every recursive solution. This article inspects it directly from Python.

The problem it solves

When f calls g, something has to remember where f was: its local variables, and the line to continue from once g returns. And when a function calls itself, each call needs its own copy, because walk(3) and walk(2) both have an n with different values.

The structure that does this is a stack of frames. A call pushes a frame; a return pops it. Only the top frame is running; everything below is paused, parked on the line after the call it made. The recursion basics article uses this to explain unwinding; here the stack itself is the subject.

The intuition

A frame holds what one call needs to resume: its arguments and local variables, and the point in the code to come back to. Three consequences follow.

• Last in, first out. The newest call is the first to finish. A call cannot return until everything it called has returned.
• Locals never collide. Each frame has its own n, so recursion does not need any special handling of variables.
• Memory is set by depth, not by call count. Frames are freed as calls return, so the space a recursive function uses is the deepest the stack ever gets. A naive Fibonacci makes tens of thousands of calls for fib(20) but never holds more than 20 frames at once. Space complexity of recursion is O(maximum depth).

A traceback is the call stack printed at the moment of an error, oldest call at the top and the failing one at the bottom, which is what "most recent call last" means. Reading it top to bottom replays how the program got there.

Python caps the depth. In CPython the default limit is 1,000 frames, readable with sys.getrecursionlimit(), and exceeding it raises RecursionError rather than crashing the process (as of October 2026). Anything else on the stack counts too: decorators and wrappers add frames of their own.

Watch it run

The animation runs the lesson's walk(3), which prints on the way in and on the way out. Every call gets a frame: its own arguments, and the line to come back to when the call it made finally returns. walk(3) prints "enter 3", then calls walk(2); its frame stays alive, parked on the line after that call. walk(2) is pushed on top, two frames now, each with its own n; they never share one. walk(1) finds n is not greater than 1, so it makes no further call, and the stack is at its deepest. It prints "leave 1" and returns: the newest frame is the first to finish. Its frame pops, and walk(2) resumes on the line it was parked on, which is exactly what the frame was storing. Then walk(3) resumes and finishes: last in, first out. The stack is empty and the output is symmetrical, a push for every enter and a pop for every leave. Frames are real memory, and about a thousand of them end in a RecursionError.

The code

The lesson's code first, then the stack read directly. inspect.currentframe() returns the running frame, and each frame's f_back points at its caller, so walking f_back lists the live stack, newest first, each frame with its own n. A traceback holds the same chain:

import inspect
import random
import sys
import traceback

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

def frames_below():
    """The live call stack, newest first, as (function, its local n) pairs."""
    out, f = [], inspect.currentframe().f_back
    while f is not None:
        out.append((f.f_code.co_name, f.f_locals.get("n")))
        f = f.f_back
    return out

def countdown(n):
    if n == 0:
        return frames_below()
    return countdown(n - 1)

print(countdown(3))
# [('countdown', 0), ('countdown', 1), ('countdown', 2), ('countdown', 3), ('<module>', None)]

def broken(n):
    return 10 // n + broken(n - 1)        # no base case: it reaches n == 0 and divides

try:
    broken(3)
except ZeroDivisionError as e:
    print([(f.f_code.co_name, f.f_locals.get("n")) for f, _ in traceback.walk_tb(e.__traceback__)])
# [('<module>', None), ('broken', 3), ('broken', 2), ('broken', 1), ('broken', 0)]

Four countdown frames are alive at once, each with its own n. The traceback lists the same chain oldest first, so the failing line is at the bottom. Next, calls versus depth, counted by a wrapper:

def tracked(fn):
    """Count every call, and the most frames of fn alive at once."""
    def wrapper(*args):
        wrapper.live += 1
        wrapper.calls += 1
        wrapper.deepest = max(wrapper.deepest, wrapper.live)
        try:
            return fn(*args)
        finally:
            wrapper.live -= 1             # this call's frame pops
    wrapper.live = wrapper.calls = wrapper.deepest = 0
    return wrapper

@tracked
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(20), fib.calls, fib.deepest)    # 6765 21891 20

print(sys.getrecursionlimit())            # 1000

@tracked
def down(n):
    return 0 if n == 0 else 1 + down(n - 1)

try:
    down(5000)
except RecursionError:
    print("RecursionError after", down.deepest, "calls")   # RecursionError after 499 calls

21,891 calls, never more than 20 alive: that is why naive Fibonacci is slow in time but cheap in stack. And down failed after 499 calls, not 1,000, because the decorator's wrapper is a frame too: two frames per call.

The seeded check, on 300 random binary search trees: a recursive size must make one call per node plus one per empty child, its deepest stack must be the tree's levels plus one, counted by a loop, and the frames walked by frames_below must agree:

def insert(node, key):
    """Random BST built with a loop, so building it needs no recursion."""
    root, cur = node or {"key": key, "l": None, "r": None}, node
    while cur:
        side = "l" if key < cur["key"] else "r"
        if cur[side] is None:
            cur[side] = {"key": key, "l": None, "r": None}
            break
        cur = cur[side]
    return root

def levels(root):
    """Brute force, no recursion: count the levels with a queue."""
    level, depth = [root] if root else [], 0
    while level:
        depth += 1
        level = [c for n in level for c in (n["l"], n["r"]) if c]
    return depth

ok = True
for seed in range(300):
    r = random.Random(seed)
    root = None
    for key in r.sample(range(1000), r.randint(0, 60)):
        root = insert(root, key)
    seen = []

    @tracked
    def size(node):
        seen.append(len(frames_below()))  # frames under this one, counted by walking them
        return 0 if node is None else 1 + size(node["l"]) + size(node["r"])

    n = size(root)
    ok &= size.calls == 2 * n + 1                          # every node, plus every empty child
    ok &= size.deepest == levels(root) + 1                 # the longest path, plus one empty child
    ok &= (max(seen) - min(seen)) // 2 + 1 == size.deepest # two frames per call: wrapper and size
print(ok)                                                  # True

The complexity

• Time: one push and one pop per call, O(1) each; the total is the number of calls.
• Space: O(maximum depth). A balanced tree recursion uses O(log n) frames; a degenerate one, or a linked list, O(n).

Where it goes wrong

• Counting calls as memory. Space is the deepest point, not the total.
• Deep input with recursion. A 10,000-node linked list or a skewed tree hits the limit; convert to an explicit stack.
• Raising the limit blindly. sys.setrecursionlimit can trade a RecursionError for a real crash of the interpreter's own stack.
• Reading tracebacks bottom-up only. The top shows how you got there.
• Expecting tail-call elimination. Python keeps every frame; see tail recursion.

When it shows up in interviews

Directly, as "what is the space complexity of your recursive solution?", where the answer is the recursion depth, and as "trace this recursive function" on a whiteboard. It also surfaces as a follow-up on deep inputs: "what happens with a million-node list?". The Python cheat sheet lists the recursion limit.

How to say it in an interview

"Every call pushes a frame holding its arguments, locals and the point to resume; a return pops it, so the newest call always finishes first. Each recursive call has its own frame, so locals never clash. Memory is set by the deepest the stack gets, not by the number of calls: naive Fibonacci makes exponentially many calls but only n frames at once, so it's O(n) space. In CPython the default depth limit is about a thousand frames, so for deep inputs I'd convert to an explicit stack."