Recursion depth limit — stack overflow: Visual walkthrough

This is the picture-first companion to the parent note. If a word here feels rushed, the prerequisites are Call stack and function frames, Recursion — base case and recursive case, and Memory model — stack vs heap.

Step 1 — What a single function call leaves behind

WHAT. When you call a function, the computer cannot just forget what it was doing. It writes a small note-card called a stack frame. That card holds three things: the call's arguments (the inputs), its local variables (scratch values), and a return address (the exact spot in the caller to jump back to when this call is done).

WHY these three and nothing else? Because those are exactly what's needed to resume the paused caller later. Arguments + locals = the call's private memory; return address = "where was I?". Drop any one and you couldn't come back correctly.

PICTURE. Look at the single yellow card below. The three labelled rows are the only contents. The card is one unit — from now on, one call = one card.

Figure — Recursion depth limit — stack overflow

Step 2 — Cards go on a LIFO pile: the call stack

WHAT. These cards are not scattered around. They are stacked into a single pile called the call stack. New calls put a card on top (this is called a push); a finished call takes the top card off (a pop).

WHY a stack and not, say, a queue? Because calls finish in the reverse order they started: the most recent call is the one currently running, so it must finish first. "Last in, first out" — LIFO — is the only ordering that matches this. The word stack is literal: think dinner plates, you only touch the top.

PICTURE. The pile below grows upward. The green arrow on the right shows a push (new card on top); the red arrow shows a pop (top card removed). The card at the very top is always the one running right now.

Step 3 — A good recursion: the pile rises, then drains

WHAT. Watch a recursion that has a base case it actually reaches. Take depth_sum:

def depth_sum(n):
    if n == 0:            # base case — the finish line
        return 0
    return n + depth_sum(n - 1)   # step moves toward 0

Calling depth_sum(3) pushes cards for n=3, 2, 1, 0. At n=0 the base case returns — no new card — so cards start popping back down.

WHY does it drain? Because each recursive call uses n - 1, strictly smaller. The argument marches $3 \to 2 \to 1 \to 0$ and hits the base case. Once one card returns, the pile can only shrink. This is the whole meaning of a reachable base case.

PICTURE. The left half shows the pile rising to height 4; the middle marks n=0 hitting the base case (green); the right half shows it draining back to zero. Notice the shape: a mountain that comes back down.

Step 4 — A broken recursion: the pile only rises

WHAT. Now remove the finish line entirely:

def boom(n):
    return boom(n + 1)    # no base case, and n grows away from any base
boom(0)

Every call makes another call before returning, so no card is ever popped. The argument goes $0 \to 1 \to 2 \to \dots$ — the wrong direction if we were hoping to reach some small base.

WHY does it never drain? A card pops only when its call returns a value. But boom's return line must first finish the inner boom(...) — which never finishes either. So the "return" for n=0 is postponed forever. The pile is all rise, no fall.

PICTURE. Compare to Step 3. There's no green base card, no peak, no descent — just an ever-taller yellow tower climbing off the top of the frame.

Step 5 — Stack memory is a small, fixed shelf

WHAT. The call stack does not live in unlimited space. The operating system hands each program a fixed, small slab of stack memory — often just 1–8 MB. Compare that to the heap (see Memory model — stack vs heap), which can be gigabytes.

WHY does this matter? Each card is not free — it occupies a chunk of that slab. Cards pile upward inside a shelf with a hard ceiling. An infinite tower (Step 4) must eventually slam into that ceiling.

PICTURE. The tall thin box is the stack shelf. The heap beside it is drawn wide to show the size gap. Cards fill the shelf from the bottom; the dashed red line near the top is the physical ceiling.

Step 6 — Python draws a soft line before the real ceiling

WHAT. CPython counts the pile height and enforces its own limit, the recursion limit (default 1000 frames), which sits below the real memory ceiling. Cross it and Python raises a catchable RecursionError instead of letting the shelf overflow.

WHY a soft line and not just wait for the crash? Two reasons. (1) A real overflow is a segfault — no message, no traceback, no way to recover. (2) A RecursionError is an ordinary exception, so try/except can catch it (see Exceptions and try-except in Python). Python trades a tiny bit of allowed depth for a graceful, debuggable failure.

PICTURE. Same shelf as Step 5, but now a yellow dashed line at "depth 1000" sits under the red physical ceiling. The tower hits the yellow line first — that's where RecursionError fires, safely below disaster.

Step 7 — The limit counts all cards, not just yours

WHAT. The limit is a total-frame count. When your recursion starts, the pile is not empty — the module, and in a REPL the interactive machinery, already sit on it. Say $k$ cards are already there. Then your recursion can only add about $1000 - k$ more.

WHY care? This is why depth_sum(998) might crash even though $998 < 1000$ : the pre-existing $k$ cards eat into your budget. The limit is per-stack, not per-function.

PICTURE. The pile starts with a small grey base of $k$ pre-existing cards. Your recursion's yellow cards stack on top, and the crash comes when the combined height reaches 1000 — so your usable slice is the shorter yellow segment.

Step 8 — The two honest fixes (not "crank the limit")

WHAT. You could call sys.setrecursionlimit(N) to raise $L$ . But raising it too far just moves the yellow line above the red physical ceiling — now the soft guard is useless and you fall into a real segfault. The robust fixes are:

Reach the base case. Make each call strictly approach the finish line (Step 3's shape).
Use iteration. A loop reuses one frame forever — the pile never grows. See Iteration vs Recursion.

WHY iteration escapes entirely? A while loop doesn't push a new card per step; it updates variables inside its single frame. Depth stays 1 no matter how many iterations. (Python does not auto-convert deep recursion for you — see Tail recursion and why Python lacks tail-call optimization.)

PICTURE. Left: recursion, a growing tower. Right: the iterative rewrite, one flat card whose inside counter changes while the pile height stays pinned at 1.

Worked example Iterative twin of

depth_sum

def depth_sum_iter(n):
    total = 0
    while n > 0:
        total += n
        n -= 1
    return total
depth_sum_iter(2_000_000)   # depth stays 1, never overflows

One frame, one total, no pile. The 2-million-step loop that would obliterate the recursion runs fine.

The one-picture summary

Everything compresses into a single storyboard: a good recursion rises then drains (mountain), a bad one rises forever into the soft line (crash), and iteration stays flat.

Recall Feynman retelling — the whole walk in plain words

Every time a function calls itself, the computer writes a little note-card ("what was I doing, and where do I go back to?") and drops it on a pile. The pile is a stack of plates: newest on top, and you can only take from the top. A good recursion — one with a real finish line it actually walks toward — builds the pile up, hits the finish line, and then takes plate after plate back off: a mountain that comes down. A broken recursion never reaches a finish line, so it just keeps stacking plates and never removes one. But the shelf holding the plates is tiny (a few megabytes), while the "big table" (the heap) is enormous — so an endless pile will hit the ceiling. If it truly hit the shelf's ceiling, the whole program would crash silently and horribly (a segfault). So Python draws a chalk line at about 1000 plates, below the real ceiling, and politely shouts "RecursionError!" when you cross it — a crash you can catch and fix. And because the pile already has a few plates on it before your function even starts, your own recursion gets a little less than 1000. The real cure is never to raise the chalk line — it's to give the recursion a finish line it reaches, or to use a plain loop that reuses one plate forever.

Connections

Recursion — base case and recursive case
Iteration vs Recursion
Call stack and function frames
Exceptions and try-except in Python
Tail recursion and why Python lacks tail-call optimization
Memory model — stack vs heap