Recursion — call stack visualization, base case, recursive case: Worked examples

The scenario matrix

Every recursive problem lives in one of these cells. The last column names the example that covers it.

#	Cell (scenario class)	What makes it tricky	Covered by
A	Normal shrink-by-one	ordinary recursive case, one branch	Example 1 (factorial)
B	Base case is the WHOLE input	input already tiny, no recursion runs	Example 2 (`fact(0)`, `summ([])`)
C	Degenerate / invalid input	negative or empty — does it stop?	Example 3 (`fact(-1)`)
D	Two base cases at once	need two stops, not one	Example 4 (Fibonacci)
E	Branching (tree-shaped) recursion	each call spawns many calls	Example 4 (Fibonacci)
F	Shrink-by-halving (limiting depth)	problem drops fast, depth is small	Example 5 (power via halving)
G	Order matters: work before vs after the call	winding vs unwinding (still linear)	Example 6 (print order)
H	Real-world word problem	translate story → base + recursive case	Example 7 (Russian dolls)
I	Exam-style twist	subtle bug you must spot	Example 8 (missing return)

Example 1 — Cell A: the ordinary shrink-by-one

Worked example Compute

fact(4) and count how many frames stack up

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

Forecast: Guess the final number, and guess how many frames exist at the deepest moment. Write them down before reading on.

Step 1 — Wind down, pushing a frame each time. fact(4) → 4 * fact(3) → 3 * fact(2) → 2 * fact(1) → 1 * fact(0). Why this step? Each call replaces $n!$ by $n \cdot (n - 1)!$ — the self-similar rule. Each pause is a frame. Look at the tower growing in the figure below (left to right, purple frames).

Step 2 — Count frames at the bottom. Frames alive: fact(4), fact(3), fact(2), fact(1), fact(0) = 5 frames. Why this step? Nothing has returned yet — every paused call still occupies memory. This is why deep recursion costs memory (see Big-O and Recursion Depth).

Step 3 — Hit the base case, then unwind. fact(0)=1, then $1 \cdot 1 = 1$ , $2 \cdot 1 = 2$ , $3 \cdot 2 = 6$ , $4 \cdot 6 = 24$ . Why this step? The stack is LIFO — Last-In-First-Out, meaning the most recently pushed frame is the first to finish and be removed. So the last-pushed frame (fact(0)) finishes first, and multiplications happen outside-in on the way back up. (See The Call Stack and Stack Frames.)

Verify: $4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24$ . ✅ Frame count = $n + 1 = 5$ . ✅

Figure — Recursion — call stack visualization, base case, recursive case

Example 2 — Cell B: the base case IS the whole input

Worked example Evaluate

fact(0) and summ([]) First, here is the summ helper we will use throughout this page — it adds up a list by peeling off the first element and recursing on the rest:

def summ(L):
    if not L:                  # base case: empty list
        return 0
    return L[0] + summ(L[1:])  # recursive case: first + sum of the rest

Forecast: How many times does the function call itself here? Guess a number.

Step 1 — Check the base condition first. For fact(0): if n == 0 is True immediately → return 1. Why this step? The base case is checked before any recursive call. If it fires, no recursion happens at all — zero self-calls.

Step 2 — Same for the empty list. summ([]): if not L is True → return 0. Why this step? An empty list is the smallest list; its sum is defined directly as $0$ .

Verify: exactly 1 frame ever exists (the outer call), 0 recursive calls. fact(0)=1, summ([])=0. ✅ This is the "already at the ground" case — no stairs to descend.

Example 3 — Cell C: degenerate / invalid input

Worked example What happens with

fact(-1)? And how do we make it safe? Forecast: Will it return a number, return None, or crash? Guess.

Step 1 — Trace the descent. n = -1: if n == 0 is False → return -1 * fact(-2). Then fact(-2), fact(-3), … Why this step? $n$ is shrinking, but it skips past $0$ — it never equals $0$ , so the base case never fires.

Step 2 — Frames pile up without limit. Python stacks frames until it hits its depth limit (~1000) → RecursionError: maximum recursion depth exceeded. Why this step? This proves the parent's warning: "smaller" is useless unless a value is caught. The stop condition, not the shrinking, is what ends recursion.

Step 3 — Fix with a robust base test.

def fact(n):
    if n <= 0:        # catches 0 AND negatives
        return 1
    return n * fact(n-1)

Why this step? Using <= catches every input that would overshoot $0$ , so fact(-1) now returns 1 safely instead of crashing.

Verify: with the fix, fact(-1) == 1 and fact(-5) == 1 (both hit the base immediately). ✅

Example 4 — Cells D & E: two base cases + branching

Worked example Compute

fib(5) where Fibonacci is $F_{0} = 0, F_{1} = 1, F_{n} = F_{n - 1} + F_{n - 2}$

def fib(n):
    if n == 0: return 0     # base case 1
    if n == 1: return 1     # base case 2
    return fib(n-1) + fib(n-2)   # TWO recursive calls

Forecast: Guess fib(5). Then guess whether this tree is taller or wider than factorial's chain.

Step 1 — Why TWO base cases? Each call splits into n-1 and n-2. If we only stopped at $0$ , the n-2 branch could leap from fib(1) straight past to fib(-1). We need to catch both $0$ and $1$ . Why this step? A branching recursion can reach the bottom from two directions, so it needs a stop for each.

Step 2 — Draw the call tree. fib(5) splits into fib(4) and fib(3); each of those splits again. See the branching tree in the figure — it fans out, unlike factorial's straight chain. Why this step? This is tree-shaped recursion — the shape that makes recursion natural (see Tree and Graph Traversal).

Step 3 — Add up from the leaves. $F_{2} = 1, F_{3} = 2, F_{4} = 3, F_{5} = 5$ . Why this step? Leaves are the base cases; every internal node is the sum of its two children.

Verify: sequence $0, 1, 1, 2, 3, 5$ → fib(5) = 5. ✅ Notice fib(3) is computed twice — that wasteful overlap motivates Fibonacci and overlapping subproblems and Memoization and Dynamic Programming.

Example 5 — Cell F: shrink-by-halving (small depth)

Worked example Fast power: compute

power(2, 10) by halving the exponent

def power(base, e):
    if e == 0:                 # base case
        return 1
    half = power(base, e // 2) # ONE call, exponent halved
    if e % 2 == 0:
        return half * half
    return half * half * base  # odd exponent: one extra base

Forecast: How many frames deep does this go for e = 10? Guess — is it 10, or fewer?

Step 1 — Halve, don't decrement. The exponent falls e = 10 → 5 → 2 → 1 → 0. Every arrow is one recursive call, so there are 4 recursive calls before the base fires at e = 0. Counting the outer power(2,10) call itself, that is 5 frames alive at the deepest moment (4 recursive calls + 1 original call). Why this step? "Recursive calls" counts how many times the function calls itself (the arrows); "frames" counts every active call including the first one you typed. Frames = recursive calls + 1. Halving reaches the base in about $⌊ lo g_{2} e ⌋$ recursive calls, so depth stays tiny. Contrast with shrink-by-one, which needs $e$ recursive calls.

Step 2 — Handle even vs odd (all cases!).

Even $e$ : $b^{e} = (b^{e /2})^{2}$ .
Odd $e$ : $b^{e} = (b^{e //2})^{2} \cdot b$ (the integer division drops the leftover 1, so we multiply one extra base). Why this step? Integer // throws away the remainder, so odd exponents lose a factor of base — we must add it back.

Step 3 — Trace power(2,10). power(2,5) needs power(2,2) needs power(2,1) needs power(2,0)=1. Build up: power(2,1)=1*1*2=2; power(2,2)=2*2=4; power(2,5)=4*4*2=32; power(2,10)=32*32=1024. Why this step? Each level squares (and sometimes multiplies one base), exactly matching the even/odd rule.

Verify: $2^{10} = 1024$ . ✅ Recursive calls $= ⌊ lo g_{2} 10 ⌋ + 1 = 3 + 1 = 4$ — much fewer than 10. ✅

Example 6 — Cell G: order matters (winding vs unwinding)

def up(n): if n < 0: return up(n-1) print(n) # AFTER the call

Note: each of these makes **exactly one** recursive call per frame — this is *linear* recursion, not branching. Only the *position* of the work changes.
**Forecast:** For `down(3)` and `up(3)`, predict both printed sequences before reading.

**Step 1 — `down`: print happens during winding.**
The `print(n)` runs *before* the recursive call, so it fires as frames go **down**: `3, 2, 1, 0`.
*Why this step?* Work placed before the recursive call executes on the descent.

**Step 2 — `up`: print happens during unwinding.**
The `print(n)` runs *after* the sub-call fully finishes, so it fires as frames **pop back up**: `0, 1, 2, 3`.
*Why this step?* Work placed after the recursive call waits for the whole subtree, then runs on the way back — this is exactly how *post-order* [[Tree and Graph Traversal]] works.

**Verify:** `down(3)` → `3,2,1,0`; `up(3)` → `0,1,2,3`. ✅ Same recursion, mirror-image output — the single line's position decides everything.

Example 7 — Cell H: real-world word problem

Worked example Russian dolls: count how many dolls are nested inside a stack

A doll is either solid (nothing inside) or hollow (contains exactly one smaller doll). Count total dolls.

def count_dolls(doll):
    if doll["inside"] is None:   # base case: solid doll
        return 1
    return 1 + count_dolls(doll["inside"])  # this doll + the rest

Forecast: For a stack of 4 nested dolls, guess the count and the number of frames.

Step 1 — Identify the base case from the story. The smallest solid doll contains nothing → it counts as 1, no recursion. Why this step? Every recursion needs the "already known" answer; here it is the innermost doll.

Step 2 — Identify the recursive case. A hollow doll = itself (1) plus whatever count_dolls returns for the doll inside. Why this step? This is the self-similar rule: "the rest of the dolls" is the same problem, one size smaller (matches the parent's Russian-doll intuition).

Step 3 — Trace 4 dolls. $1 + (1 + (1 + 1)) = 4$ . Why this step? Four frames pile up, the innermost returns 1, and each hollow doll adds 1 on the way up.

Verify: total = 4, frames = 4. ✅ Units: dolls in = dolls counted.

Example 8 — Cell I: exam-style twist (spot the bug)

Worked example This "recursive sum" returns

None. Find the bug.

def summ_buggy(L):
    if not L:
        return 0
    L[0] + summ_buggy(L[1:])   # <-- look closely

Forecast: What does summ_buggy([4, 2, 7]) return? Guess before tracing.

Step 1 — Check the base case. if not L: return 0 is fine — the empty list correctly returns 0. Why this step? Rule out the usual suspect first; the stop condition is correct here.

Step 2 — Inspect the recursive line. L[0] + summ_buggy(L[1:]) computes a value but there is no return. Python discards it and falls off the end → returns None. Recursion does not hand a value back automatically; you must explicitly return (or store) the sub-call's result. Why this step? Once the base case returns 0, the next line up tries L[0] + None, which would itself raise a TypeError — but for a single-element list the buggy function returns None cleanly because its recursive line's value is simply thrown away.

Step 3 — Fix it.

def summ_fixed(L):
    if not L:
        return 0
    return L[0] + summ_fixed(L[1:])

Why this step? Now the combined value travels back up the stack instead of being thrown away.

Verify: buggy version → None; fixed version → $4 + 2 + 7 = 13$ . ✅

Recall Quick self-test on the matrix

Which cell is fact(0)? ::: Cell B — base case is the whole input, zero recursive calls. Which cell would fib fall into and why two base cases? ::: Cells D & E — branching recursion, and the n-2 branch can leap past 0, so we catch both 0 and 1. Moving print after the recursive call changes which phase it runs in? ::: From winding (descent) to unwinding (return), reversing the output order. Why does halving-power need far fewer frames than shrink-by-one? ::: It reaches the base in about log₂(e) recursive calls instead of e.