Recursion depth limit — stack overflow: Worked examples

Look at the picture below: it traces the exact function of Example 1, countdown(3). Read it top-to-bottom: each call lays down one black plate, and the moment the base case countdown(0) fires (the red plate) is the tallest the stack ever gets — four plates high. The dashed line near the top is the ~1000-frame limit; this little example is nowhere near it, but every crash on this page is just this same picture grown past that line.

Figure — Recursion depth limit — stack overflow

We will refer back to this "plate pile" repeatedly — it is the mental model behind every cell of the matrix.

The scenario matrix

Every recursion problem lands in one of these cells. The examples below are labelled with the cell they cover.

Cell	Situation	What decides the outcome
A	Base case present and reached, depth < limit	Runs fine, returns a value
B	Base case correct but depth > limit	`RecursionError` even though logic is right
C	Base case missing (infinite)	`RecursionError` fast, always
D	Base case exists but never approached	`RecursionError` — the sneaky bug
E	Zero / degenerate input (`n = 0`, empty list)	Hits base immediately, depth = 1
F	Negative / wrong-direction input	Overshoots the base, runs away
G	Branching recursion (calls itself twice)	Depth ≠ number of calls — depth is the tallest path
H	Limit raised deliberately for deep-but-finite work	Runs, but risks a hard segfault
I	Real-world word problem	Translate story → depth
J	Exam twist — count exact frames, off-by-one	The `1000` is total frames, not per-function
K	Mutual (co-)recursion — `is_even`↔`is_odd`	Two functions bounce; depth is the combined chain, still one shared stack

The single idea threaded through all of them. First one symbol to earn:

Cell A + E — base reached, and the degenerate input

Worked example Example 1 —

countdown that finishes (Cells A, E)

def countdown(n):
    if n == 0:            # base case
        return "liftoff"
    return countdown(n - 1)
countdown(3)
countdown(0)              # degenerate input

Forecast: How deep does countdown(3) stack? What does countdown(0) do — does it even recurse?

Trace countdown(3). Frames pushed: n=3, n=2, n=1, n=0 — exactly the four plates in the figure at the top of this page (the base plate n=0 is red). Why this step? Each call subtracts 1, so we strictly approach the base — the plates will come back off in reverse order as each return fires.
Count peak depth. At the moment n=0 runs, four frames are alive → $d = 4 = n + 1$ . Why this step? Depth is frames stacked at once; for a linear chain from $n$ to $0$ that is $n + 1$ .
countdown(0). The if n == 0 fires immediately, returns "liftoff", no recursive call. Why this step? The degenerate input is the base itself — only the red plate exists, $d = 1$ , the smallest possible.

Verify: peak depth for countdown(3) $= 3 + 1 = 4 \leq 1000$ . Runs fine. countdown(0) recurses 0 times.

Cell C — no base case (pure infinite)

The figure below overlays two runs on the same plate-height axis: the healthy countdown (black, rises to $d = 4$ then falls) versus boom (red, climbs forever straight through the dashed limit line). This single picture is the shape of every runaway on this page — Cells C, D and F all trace that red line.

Worked example Example 2 —

boom with no finish line (Cell C)

def boom(n):
    return boom(n + 1)   # nothing ever stops it
boom(0)

Forecast: Roughly which call number triggers the crash?

Look for a base case. There is none — no if ... return. Why this step? A recursion without a stopping return can only end by hitting the limit.
Depth per call. Each call pushes a plate and never pops (the inner call must finish first, but it never does). $d$ = call number. Why this step? This is Cell C's signature: the red line in the figure above — a monotone climb, no relief.
Crash point. With $k$ pre-existing frames, it dies around call $1000 - k$ . Why this step? That is the inequality from the formula box, saturated ( $d = 1000 - k$ ).

Verify: with a clean start ( $k \approx$ a handful), crash near call ≈ 996–999, never past 1000. RecursionError guaranteed.

See Recursion — base case and recursive case — Cell C is exactly "forgot the base case".

Cell D — base exists but is never approached (the sneaky one)

Worked example Example 3 — the base case that's a decoy (Cell D)

def stuck(n):
    if n == 0:
        return 1          # a real base case...
    return stuck(n + 1)   # ...but we move AWAY from it
stuck(5)

Forecast: There is an if n == 0. Does that save us?

Check direction of travel. We start at 5 and call stuck(6), stuck(7), ... Why this step? The base is at 0; every step increases $n$ , so we never land on it — the plate pile follows the red runaway line of the figure above, just like Cell C.
Compare to Cell C. Behaviour is identical to no-base-case: monotone climb to the limit. Why this step? A base case unreachable in practice is worth exactly nothing.
The fix. Change to stuck(n - 1) and base n <= 0. Why this step? Now each call strictly approaches 0 (see Recursion — base case and recursive case).

Verify: stuck(5) raises RecursionError; the fixed stuck(n-1) version returns 1 and reaches peak depth $5 + 1 = 6$ .

Cell F — wrong-direction / negative input

Worked example Example 4 — a correct function fed a bad number (Cell F)

def down(n):
    if n == 0:
        return 0
    return down(n - 1)
down(-4)

Forecast: The function is fine for positives. What happens for $n = - 4$ ?

Follow the sign. down(-4) → down(-5) → down(-6) → ... Why this step? Subtracting 1 from a negative moves further from 0, not toward it — the same red runaway climb from the Cell C figure.
Recognise the cell. For negative input this correct-looking function behaves like Cell D — it overshoots the base and runs away. Why this step? The base n == 0 is only reachable from $n \geq 0$ .
The robust fix. Use if n <= 0: return 0. Why this step? <= catches every value at or below the base, so negatives stop immediately.

Verify: down(-4) raises RecursionError; with n <= 0 it returns 0 at peak depth 1 (base fires on the first call).

Cell G — branching recursion (depth ≠ call count)

Worked example Example 5 — Fibonacci: many calls, shallow stack (Cell G)

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)
fib(6)

Forecast: fib(6) makes dozens of calls. Does it risk a stack overflow?

Count total calls. fib(6) triggers 25 calls in total. Why this step? People fear this number — but total calls is not what the limit checks.
Find the tallest path, not the widest. Python evaluates fib(n-1) fully (reaching down to fib(1)) before touching fib(n-2). The deepest single chain is $n \to n - 1 \to \dots \to 1$ . Why this step? Depth is frames stacked at one instant; the two branches are never both fully open at once.
Compute peak depth. Longest chain from 6 down to the base = frames for $n = 6, 5, 4, 3, 2, 1$ → $d =$ 6. Why this step? Peak depth for two-way branching is the length of the tallest root-to-leaf path, not the total node count — read it straight off the red path in the tree below.

Verify: fib(6) = 8; total calls $= 25$ ; peak depth $d = 6$ , comfortably under 1000. Branching explodes time, not depth.

Cell B + J — correct logic, depth over the limit, exact-count twist

Worked example Example 6 — deep-but-legal sum, and the exam off-by-one (Cells B, J)

def depth_sum(n):
    if n == 0:
        return 0
    return n + depth_sum(n - 1)
depth_sum(2000)   # RecursionError — logic fine, depth too big

Forecast: The maths is perfect. Why does depth_sum(2000) still crash — and what is the largest n that works from a fresh REPL with the default limit?

Peak depth. depth_sum(n) reaches $d = n + 1$ (Cell A rule). For $n = 2000$ that is 2001. Why this step? $2001 > 1000$ , so the plate pile passes the dashed limit line mid-descent even though every line is correct — this is Cell B.
Solve for the largest safe $n$ . From the formula box, $d \leq recursionlimit - k$ with $d = n + 1$ , so $n + 1 \leq 1000 - k \Rightarrow n \leq 999 - k$ . Why this step? The limit counts all frames; $k$ are already present when you call. This is the Cell J twist.
Plug in $k = 2$ (module + the calling frame): $n \leq 999 - 2 = 997$ . Why this step? It shows the answer is not 999 — the pre-existing frames steal room, matching the parent's "≈ 1000 − k".

Verify: peak depth for $n = 2000$ is $2001 > 1000$ → RecursionError. The safe- $n$ bound $n \leq 999 - k$ gives $n \leq 997$ for $k = 2$ .

Cell A (iterative escape) — one frame forever

Worked example Example 7 — the iterative rewrite (Cell A, no growth)

def depth_sum_iter(n):
    total = 0
    while n > 0:
        total += n
        n -= 1
    return total
depth_sum_iter(2_000_000)

Forecast: Same maths as Example 6 but a loop. How deep does the stack go for two million?

Count frames. The while loop reuses the single frame of depth_sum_iter. Why this step? A loop updates variables in place — it never pauses one call to start another, so the plate pile is exactly one plate tall the whole time.
Depth is constant. No matter how big n is, $d$ stays 1. Why this step? This is the whole point of Iteration vs Recursion: iteration trades stack growth for a loop counter.
Check it still returns the right total. depth_sum_iter(4) should equal the recursive depth_sum(4): $4 + 3 + 2 + 1 = 10$ . Why this step? A rewrite must give the same value, only a shallower depth — same answer, $d = 1$ instead of $d = n + 1$ .

Verify: depth_sum_iter(4) = 4+3+2+1 = 10 (matches depth_sum(4)); peak depth $d$ stays 1 even for 2,000,000. No RecursionError possible.

Cell K — mutual (co-)recursion, one shared stack

Worked example Example 8 —

is_even and is_odd bounce off each other (Cell K)

def is_even(n):
    if n == 0: return True
    return is_odd(n - 1)
def is_odd(n):
    if n == 0: return False
    return is_even(n - 1)
is_even(4)

Forecast: Two different functions call each other. Do they each get their own private stack limit?

Trace the bounce. is_even(4) → is_odd(3) → is_even(2) → is_odd(1) → is_even(0) → True. Why this step? Each step drops $n$ by 1, alternating functions — the plate pile does not care which function laid the plate; it's one shared stack.
Count combined depth. Five frames alive at the peak: is_even(4), is_odd(3), is_even(2), is_odd(1), is_even(0). So $d = n + 1 = 5$ . Why this step? The formula box's $d$ counts all frames on the one stack, so two mutually-recursive functions share the same 1000-frame budget, not two separate ones.
Same failure modes apply. Forget a base case in either function and you get Cell C; feed a negative and you get Cell F. Why this step? Mutual recursion is not a new danger — it's the same plate pile with two labels alternating.

Verify: is_even(4) is True; is_odd(4) is False; peak depth $d = 4 + 1 = 5 \leq 1000$ .

Cell H — raising the limit for deep-but-finite work

Worked example Example 9 — deep-but-finite recursion, limit raised on purpose (Cell H)

import sys
sys.setrecursionlimit(3000)     # deep-but-finite: 1500 + headroom
def depth_sum(n):
    if n == 0:
        return 0
    return n + depth_sum(n - 1)
depth_sum(1500)                 # now legal: needs 1501 frames

Forecast: depth_sum(1500) needs peak depth 1501 — over the default 1000. Is raising the limit the blind mistake the parent warned about, or the right call here?

Is the depth finite? Yes — $d = n + 1 = 1501$ , a known, bounded number. Why this step? Cell H is legitimate only when depth is finite and you can name its maximum.
Choose the new limit. Need $limit > d + k = 1501 + k$ . Set $3000$ — roughly double — leaving generous headroom for the $k$ pre-existing frames. Why this step? From the formula box, safety is $d + k \leq recursionlimit$ ; doubling the known peak is comfortable slack.
Why this is not the blind mistake. The blind version raises the limit to "fix" an infinite (Cell C/D) recursion and sails into a segfault. Here the recursion terminates at $d = 1501$ . Why this step? The danger is unbounded depth, not a large-but-finite one.

Verify: required limit $> 1501 + k$ ; chosen $3000 \geq 1502$ → safe. Peak depth $d = 1500 + 1 = 1501$ , a finite number the raised limit accommodates.

Cell I — a real-world word problem

Worked example Example 10 — the nested-folder size walk (Cell I)

Story: A backup tool walks a directory tree, recursing into each sub-folder to total up file sizes. On one user's machine the folders are nested 1500 deep. The tool has a correct base case (a folder with no sub-folders returns just its own file sizes). Sizes on the three files at the bottom are 1, 2, and 4 bytes. Will the default-limit tool crash, and what total should it report on that little three-file leaf?

def tree_size(folder):
    if folder.is_leaf():                       # base: no sub-folders
        return sum(folder.file_sizes)          # e.g. [1, 2, 4]
    return sum(tree_size(sub) for sub in folder.subfolders)

Forecast: Translate "1500 folders deep" into a peak depth. Does it fit under 1000?

Translate the story to depth. Each nesting level = one recursive call = one frame. 1500 levels → peak depth $d = 1500$ (plus the leaf frame ≈ 1501). Why this step? A word problem is solved by mapping the real structure onto the plate pile — folders deep is depth.
Compare to the default limit. $1501 > 1000$ , so with the default limit the correct tool crashes with RecursionError — this is a real Cell B situation triggered by real data. Why this step? The bug is not in the code; the input's depth exceeds the budget.
Total the leaf. For the bottom three-file folder, sum([1, 2, 4]) = 7 bytes. Why this step? Sanity-check the base case gives the obvious hand-computed answer, so we trust the recursion's leaves.

Verify: peak depth $\approx 1501 > 1000$ → crashes on default limit (fix: sys.setrecursionlimit(3000) as in Example 9, since 1500 is finite). The leaf total sum([1,2,4]) = 7 bytes.

Cell A + Exceptions — catch it and recover

Worked example Example 11 — graceful

try/except, and what it returns on overflow (Cell A, defensive)

import sys
def safe_factorial(n):
    try:
        if n <= 1:
            return 1
        return n * safe_factorial(n - 1)
    except RecursionError:
        return None            # signal "too deep to compute"
safe_factorial(5)              # normal path
safe_factorial(100_000)        # overflow path (way past the limit)

Forecast: For $n = 5$ we're nowhere near the limit — what does the try/except actually do here, and what comes back for a huge $n$ that does overflow?

Normal path. $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$ , base at n <= 1, peak depth $d = 5$ . Why this step? Small $n$ → Cell A, the except never fires, so the try is invisible here.
Overflow path. For $n = 100000$ the plate pile passes the ~1000 line; the inner call raises RecursionError. That error propagates up to the nearest try, which catches it and runs the except branch. Why this step? RecursionError is a normal exception, so it unwinds the stack to the handler exactly like any other (see Exceptions and try-except in Python) — this is precisely why Python uses a soft, catchable limit instead of a hard segfault.
What is returned. On overflow the function returns None, letting the caller detect "too deep" and react instead of crashing. Why this step? Recovery beats a dead program — the soft limit is what makes this recovery possible at all.

Verify: safe_factorial(5) = 120; safe_factorial(1) = 1; peak depth for $n = 5$ is $d = 5 \leq 1000$ ; the overflow path returns None (a RecursionError is caught, not propagated).

The 80/20 of every cell

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