Classic recursion — factorial, Fibonacci, binary search: Worked examples

The scenario matrix

Every recursion problem lives somewhere in a small grid of situations. If a walkthrough never showed you a cell, you'd be guessing when you hit it. Here is the full grid we will cover — each cell names the tricky thing that could go wrong there.

#	Machine	Scenario class	The tricky thing
A	factorial	typical `n>0`	the multiplications pile up, then unwind
B	factorial	boundary `n=0`	base case fires immediately, no recursion
C	factorial	invalid `n<0`	there is no base case below 0 → infinite recursion
D	fibonacci	boundary `n=0, n=1`	two base cases, why two
E	fibonacci	typical `n≥2` naive	the call tree branches and repeats work
F	fibonacci	same `n` memoized	each subproblem computed once
G	binary search	target present	halving converges onto the index
H	binary search	target absent	the range collapses (`lo>hi`) → `-1`
I	binary search	target at an edge	first or last element, off-by-one danger
J	binary search	unsorted input	the "throw away a half" logic is invalid
K	word problem	real-world	phone-book / dictionary lookup as binary search

The examples below are tagged with the cell(s) they hit. Together they touch A–K.

Example 1 — factorial, typical case `n=4` (cell A)

Worked example Compute

factorial(4) Forecast first: before reading on, guess: how many nested calls happen, and what is the final number?

Recall the code:

def factorial(n):
    if n == 0:                     # base case
        return 1
    return n * factorial(n - 1)    # recursive case

Step 1 — descend, piling calls onto the stack. Why this step? Each call can't finish its multiplication until the smaller call returns, so it parks itself and waits. $4! = 4 \cdot 3! = 4 \cdot (3 \cdot 2!) = 4 \cdot (3 \cdot (2 \cdot 1!)) = 4 \cdot (3 \cdot (2 \cdot (1 \cdot 0!)))$

Step 2 — hit the base case. Why this step? n has walked $4 \to 3 \to 2 \to 1 \to 0$ . At n==0 we return 1 directly — the chain stops. This is the deepest point; look at the bottom of the figure.

Step 3 — unwind, multiplying on the way up. Why this step? Now each parked call receives its child's answer and does its one multiplication: $0! = 1 \to 1 \cdot 1 = 1 \to 2 \cdot 1 = 2 \to 3 \cdot 2 = 6 \to 4 \cdot 6 = 24$

Answer: 24. (Nested calls: 4 recursive calls plus the base, so 5 frames deep.)

Verify: $4! = 4 \times 3 \times 2 \times 1 = 24$ . ✓ Matches the plain definition.

Example 2 — factorial boundary `n=0` (cell B)

Example 3 — factorial invalid `n=-3` (cell C, degenerate)

Worked example What does

factorial(-3) do? Forecast: does it return a number, or crash? Why?

Step 1 — try to match the base case. Why this step? if n == 0 with n = -3 is False. So we recurse: -3 * factorial(-4).

Step 2 — watch n run away from the base. Why this step? Next call has n = -4, then -5, -6, … Each is further from 0, not closer. The base case is unreachable.

Step 3 — the stack overflows. Why this step? Frames pile up forever. Python caps recursion depth (~1000 by default) and raises:

RecursionError: maximum recursion depth exceeded

Answer: it raises RecursionError.

Verify (the lesson): a recursive case must always move the input toward the base. Here $n - 1$ moves away from $0$ when $n < 0$ . A robust version guards the input:

if n < 0:
    raise ValueError("factorial is undefined for negatives")

This is cell C's point: every direction of input must terminate.

Example 4 — Fibonacci base cases `n=0, n=1` (cell D)

Worked example Compute

fib(0) and fib(1) Forecast: why can't Fibonacci get away with one base case like factorial?

Recall:

def fib(n):
    if n < 2:                        # covers n=0 AND n=1
        return n
    return fib(n - 1) + fib(n - 2)

Step 1 — fib(0). 0 < 2 is True, return 0. No recursion. Step 2 — fib(1). 1 < 2 is True, return 1. No recursion.

Step 3 — why two values are needed. Why this step? The recursive case is fib(n-1) + fib(n-2) — it reaches back two steps. If we only knew fib(0), then computing fib(1) would need fib(-1), which never terminates. So we must pre-load two known answers. The single test n < 2 cleverly returns n itself, giving $F_{0} = 0$ and $F_{1} = 1$ in one line.

Answers: fib(0)=0, fib(1)=1.

Verify: the sequence starts $0, 1, 1, 2, 3, \dots$ ✓

Example 5 — naive Fibonacci `fib(5)`, the repeated work (cell E)

Worked example Compute

fib(5) naively and count the calls Forecast: the answer is a small number, but guess how many total calls the naive version makes.

Step 1 — expand the recurrence. $F_{5} = F_{4} + F_{3}, F_{4} = F_{3} + F_{2}, F_{3} = F_{2} + F_{1}, F_{2} = F_{1} + F_{0}$

Step 2 — draw the call tree. Why this step? The tree exposes the disease: the same subproblem appears in unrelated branches. Look at how many times fib(2) and fib(1) appear.

Step 3 — read off the value. Unwinding from the leaves: $F_{2} = 1, F_{3} = 2, F_{4} = 3, F_{5} = 5$ .

Answer: fib(5) = 5.

Step 4 — count the calls. The number of calls for fib(n) is $2 F_{n + 1} - 1$ . For $n = 5$ : $2 F_{6} - 1 = 2 \cdot 8 - 1 = 15$ calls to produce one small number.

Verify: $F_{5} = 5$ (sequence $0, 1, 1, 2, 3, 5$ ). Call count $= 2 F_{6} - 1 = 15$ . ✓ This exponential blow-up ( $Θ (φ^{n})$ ) is the trap the parent note warned about. See Big-O Notation.

Example 6 — memoized Fibonacci `fib(30)` (cell F)

Worked example Compute

fib(30) with memoization Forecast: naive fib(30) makes ~2.7 million calls. With a cache, how many distinct subproblems are there?

def fib(n, memo={}):
    if n < 2: return n
    if n in memo: return memo[n]
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

Step 1 — first time each fib(k) is asked, compute and store. Why this step? The cache memo remembers answers. The first branch that needs fib(k) computes it; every later branch reads it instantly.

Step 2 — count distinct subproblems. Why this step? The subproblems are exactly fib(0), fib(1), …, fib(30) — that's 31 distinct values, each done once → $Θ (n)$ instead of $Θ (φ^{n})$ .

Step 3 — the value. $F_{30} = 832040$ .

Answer: fib(30) = 832040.

Verify: $F_{30} = 832040$ (checked in VERIFY). See Memoization and Dynamic Programming for why caching turns the tree into a line.

Example 7 — binary search, target present (cell G)

Worked example Find

target = 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] Forecast: the list has 10 items. Guess the maximum number of comparisons needed ( $⌈ lo g_{2} 10 ⌉ = ?$ ).

def binary_search(arr, target, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo > hi: return -1
    mid = (lo + hi) // 2
    if arr[mid] == target: return mid
    elif arr[mid] < target: return binary_search(arr, target, mid+1, hi)
    else:                    return binary_search(arr, target, lo, mid-1)

Step 1 — probe the middle, throw away a half. Why this step? On a sorted list, comparing to the middle tells you which half can't contain the target, so you discard it. Follow the shrinking window in the figure.

call	lo	hi	mid	arr[mid]	decision (Why?)
1	0	9	4	16	$16 < 23$ → go right, `lo=5`
2	5	9	7	56	$56 > 23$ → go left, `hi=6`
3	5	6	5	23	found → return `5`

Answer: index 5. Took 3 comparisons (and $⌈ lo g_{2} 10 ⌉ = 4$ is the worst case, so 3 is within bound).

Verify: arr[5] == 23. ✓

Example 8 — binary search, target absent (cell H, degenerate collapse)

Worked example Find

target = 40 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] Forecast: 40 isn't in the list. How does the recursion know to stop, and what does it return?

Step 1 — narrow as usual.

call	lo	hi	mid	arr[mid]	decision
1	0	9	4	16	$16 < 40$ → `lo=5`
2	5	9	7	56	$56 > 40$ → `hi=6`
3	5	6	5	23	$23 < 40$ → `lo=6`
4	6	6	6	38	$38 < 40$ → `lo=7`

Step 2 — the range collapses. Why this step? Now lo=7, hi=6, so lo > hi is True. The window is empty — there's nowhere left the target could hide. This is the base case for "not found".

Answer: -1.

Verify: 40 is genuinely not in the array, and lo > hi correctly signals the empty range. ✓ This shows the absent path always terminates: each step shrinks hi - lo, so it must reach the empty case.

Example 9 — binary search at the edges (cell I, off-by-one)

Worked example Find

target = 2 (first element) and target = 91 (last element) Forecast: off-by-one bugs live at the ends. Does the code reach index 0 and index 9 correctly?

Find 2 (leftmost):

call	hi	mid	arr[mid]	decision
1	9	4	16	$16 > 2$ → `hi=3`
2	3	1	5	$5 > 2$ → `hi=0`
3	0	0	2	found → return `0`

Find 91 (rightmost):

call	lo	hi	mid	arr[mid]	decision
1	0	9	4	16	$16 < 91$ → `lo=5`
2	5	9	7	56	$56 < 91$ → `lo=8`
3	8	9	8	72	$72 < 91$ → `lo=9`
4	9	9	9	91	found → return `9`

Answers: 2 → index 0; 91 → index 9.

Why the edges are safe: the mid+1 and mid-1 moves guarantee lo and hi still land exactly on index 0 and 9. If the code had used mid instead of mid±1, it could loop forever on a one-element window — that's the classic off-by-one bug this example rules out.

Verify: arr[0]==2 and arr[9]==91. ✓

Example 10 — binary search on UNSORTED input (cell J, invalid precondition)

Worked example Find

target = 8 in [38, 2, 91, 8, 16, 5] (NOT sorted) Forecast: the value 8 is present (at index 3). Will binary search find it?

Step 1 — probe the middle blindly.

call	lo	hi	mid	arr[mid]	decision (invalid!)
1	0	5	2	91	$91 > 8$ → go left, `hi=1`
2	0	1	0	38	$38 > 8$ → go left, `hi=-1`

Step 2 — the range collapses onto "not found". Why this fails: the algorithm assumes everything left of mid is smaller. Here that's false — 8 lives at index 3, to the right of mid=2, but the comparison $91 > 8$ tricked it into discarding the right half. It never even looks where the answer is.

Answer: -1 — WRONG. The true index is 3.

Verify: 8 occurs at index 3 in the given list, yet binary search returns -1. ✓ (the bug is real). Fix: sort first (see Sorting Algorithms), costing $Θ (n lo g n)$ , or use linear search. This is exactly the parent note's steel-man trap.

Example 11 — real-world word problem (cell K)

Worked example The phone-book lookup

A physical phone book has 1,000,000 sorted names. Your friend uses linear search (page by page from the start). You use binary search (open the middle, tear away half, repeat). In the worst case, how many "opens" does each of you need?

Forecast: guess the two numbers before computing.

Step 1 — linear search worst case. Why: if the name is on the last page, you check all million. $comparisons_{linear} = 1, 000, 000$

Step 2 — binary search worst case. Why: each open halves what remains: $1, 000, 000 \to 500, 000 \to \dots \to 1$ . The number of halvings is $⌈ lo g_{2} 1, 000, 000 ⌉$ . $lo g_{2} 1, 000, 000 \approx 19.93 \Rightarrow 20 opens$

Answer: linear = 1,000,000 opens; binary = 20 opens.

Verify: $2^{20} = 1, 048, 576 \geq 1, 000, 000 > 2^{19} = 524, 288$ , so $⌈ lo g_{2} 1 0^{6} ⌉ = 20$ . ✓ This 50,000× speed-up is what "logarithmic" feels like — see Divide and Conquer and Recursion vs Iteration.

Recall Quick self-test on the matrix

factorial(-2) does what, and why? ::: Raises RecursionError — n-1 moves away from the base case 0, so it never terminates. Why does Fibonacci need two base cases but factorial needs one? ::: fib reaches back two steps (n-1 and n-2), so two known starting values are required or it recurses below 0. What does binary search return, and how does it detect, a missing target? ::: -1, detected when the range collapses to lo > hi (empty window). Binary search returned -1 for a value you know is present — likely cause? ::: The array wasn't sorted; the halving logic is invalid on unsorted data. Worst-case comparisons of binary search on 1,000,000 sorted items? ::: 20 (ceil of log base 2 of 1,000,000).

Connections

Classic recursion — factorial, Fibonacci, binary search (index 1.2.38) — the parent this deep-dive expands
Big-O Notation — where $Θ (n)$ , $Θ (lo g n)$ , $Θ (φ^{n})$ come from
Memoization and Dynamic Programming — Example 6's cache
Divide and Conquer — binary search & the phone book
Recursion vs Iteration — trade-offs behind these traces
The Call Stack and Stack Frames — the pile-and-unwind in Examples 1 & 3
Sorting Algorithms — the fix for the unsorted-input trap