Classic recursion — factorial, Fibonacci, binary search: Visual walkthrough

We only need a handful of ideas, and we will earn each one before we use it. Let us begin at absolute zero.

Definition Two counting symbols we will keep using

$c$ ::= a fixed amount of "one step" of work — say, doing a single comparison or a single multiplication. It does not grow with the input; it is just "one small chunk of effort". We write $c$ instead of a specific number of nanoseconds because the exact number does not matter — only how the total grows.
$Θ (\cdot)$ (read "Theta of") ::= ==a label for how fast the total work grows as the input $n$ gets big==, ignoring constant multipliers. $Θ (n)$ means "work grows in proportion to $n$ " (double $n$ , roughly double the work). $Θ (lo g n)$ means "work grows like the number of times you can halve $n$ ". $Θ (φ^{n})$ means "work multiplies by about $φ$ every time $n$ goes up by one" — explosive. Full treatment in Big-O Notation.

WHY these two. Recurrences like $T (n) = T (n - 1) + c$ literally say "the work for size $n$ is the work for size $n - 1$ , plus one small chunk $c$ ." $Θ$ is how we turn that sentence into a growth rate.

Step 1 — What "call itself on a smaller problem" actually looks like

WHAT. A function is a named machine: you feed it an input, it hands back an output. When we write $factorial (3)$ we mean "run the factorial machine with the number $3$ inside it".

WHY a smaller copy. Look at the definition the parent gave us: $answer we want n! = the current number n \times the SAME question, one size smaller (n - 1)!$ Term by term: $n!$ is what we are trying to compute; $n$ is the number we currently hold; and $(n - 1)!$ is the exact same question asked about a number one smaller. That last piece is the whole trick — the problem contains a shrunken copy of itself.

PICTURE. Below, each machine is a rounded box. A box cannot finish until the smaller box inside it finishes. The boxes nest like Russian dolls, shrinking $3 \to 2 \to 1 \to 0$ , until the smallest doll ( $0$ ) needs no help.

Figure — Classic recursion — factorial, Fibonacci, binary search

Step 2 — The stack fills going DOWN

WHAT. When $factorial (3)$ needs $factorial (2)$ , it pauses itself and writes a note: "I still owe a multiplication by $3$ once the answer comes back." That note is a stack frame — a little memory box the machine keeps.

WHY it must pause. The multiplication $3 \times (\dots)$ cannot happen yet, because the $(\dots)$ is not known. So the machine parks the half-done work and dives deeper. Each dive adds one frame.

PICTURE. Read the tower top-to-bottom. Each new call stacks a frame below the last (this is the "piling up" the parent mentioned). Notice the pending work written on the right of every frame — that is what waits.

$factorial (3) \Rightarrow factorial (2) \Rightarrow factorial (1) \Rightarrow base case, no deeper dive factorial (0)$

Each $\Rightarrow$ is "I paused and asked a smaller me". The chain stops the instant it hits $0$ .

Step 3 — The stack empties going UP (the unwind)

WHAT. The base case $factorial (0)$ returns $1$ immediately. Now the parked frames wake up bottom-first, each doing its one waiting multiplication.

WHY bottom-first. The frame added last is the one whose smaller question got answered first, so it resumes first. This is exactly why a stack is used: last in, first out.

PICTURE. Same tower as Step 2, now read bottom-to-top with green return arrows. Watch the number $1$ travel upward, getting multiplied at each floor: $1 \to 1 \times 1 \to 2 \times 1 \to 3 \times 2$ .

$0! 1 \times 1 1! 1 \times 2 2! 2 \times 3 3! 6$

Each labelled brace is the value a floor returns; each arrow is the multiplication that floor was waiting to do. The final $6$ is $3!$ .

Recall Why factorial costs

$Θ (n)$ Its recurrence is $T (n) = T (n - 1) + c$ : "the work for $n$ equals the work for $n - 1$ plus one chunk $c$ (a single multiply)." The tower has one floor per number from $n$ down to $0$ : that is $n + 1$ floors, each costing $c$ . Adding $c$ that many times gives $(n + 1) \cdot c$ , which grows in step with $n$ → $Θ (n)$ . See Big-O Notation.

Step 4 — Fibonacci: the box that opens TWO boxes

WHAT. Factorial opened one smaller box. Fibonacci's rule opens two: $F_{n} = one step back F_{n - 1} + two steps back F_{n - 2}$ $F_{n}$ is the number we want; $F_{n - 1}$ and $F_{n - 2}$ are the two smaller questions we must ask. Because the rule reaches back two steps, we need two base cases ( $F_{0} = 0$ , $F_{1} = 1$ ) — otherwise a branch would fall below $F_{0}$ and never land.

WHY this makes a tree, not a tower. One box that spawns two boxes, each of which spawns two more, is not a straight line — it branches. That branching is the source of all the trouble.

PICTURE. The call tree for $F_{4}$ . Follow the split at every node. Circle the two nodes labelled $F_{2}$ : they are computed in separate branches that never talk to each other.

Step 5 — WHY the naive tree is slow (the $φ^{n}$ derivation)

WHAT. Let $C (n)$ be the number of calls the naive $fib (n)$ makes. Every call to $fib (n)$ (for $n \geq 2$ ) makes exactly the calls of $fib (n - 1)$ plus the calls of $fib (n - 2)$ , plus itself: $calls for n C (n) = left branch C (n - 1) + right branch C (n - 2) + this call itself 1$ That is the same shape as the Fibonacci recurrence itself — the count of calls grows like Fibonacci numbers grow.

WHY it grows like $φ^{n}$ , not $2^{n}$ . If every box opened two full-size boxes, the count would double each level → $2^{n}$ . But it does not: one branch is size $n - 1$ and the other is only $n - 2$ — the second branch is shorter, so the tree is lopsided, not a full doubling. The true growth rate is the number $φ$ that satisfies the sequence's own multiply-rule: $φ^{2} = φ + 1 ⟹ φ = \frac{1 + 5}{2} \approx 1.618$ Term by term: $φ^{2}$ is "two steps of growth", and it equals " $φ$ (one step) plus $1$ " — the exact reach-back-one-and-two pattern. So each increase of $n$ by one multiplies the work by about $φ \approx 1.618$ (not $2$ ), giving $Θ (φ^{n})$ . Slower than doubling, but still explosive.

PICTURE. The same tree, now with repeated subtrees painted the same colour. Every extra copy of a colour is pure wasted recomputation — and the two branches below any node are visibly unequal in height, which is why the base is $φ$ and not $2$ .

Step 6 — Memoization: cross out the duplicates

WHAT. Keep a notebook (memo) mapping " $k$ " → " $F_{k}$ ". Before computing $F_{k}$ , peek in the notebook. If it's there, hand it back instantly; if not, compute once and write it down.

WHY it collapses the tree. After the first time we solve $F_{2}$ , every other $F_{2}$ node becomes a single instant lookup — its whole subtree is deleted. The branching tree flattens into a slim path.

PICTURE. The $F_{4}$ tree with duplicate subtrees crossed out and replaced by a "cache hit" tag. What's left is a thin chain — only $n$ genuine computations.

$naive: Θ (φ^{n}) notebook memoized: Θ (n)$

The arrow reads "adding the notebook turns exponential into linear."

Step 7 — Binary search: throwing away half a picture at a time

WHAT. Given a sorted list, we compare the target to the middle element and discard the half it cannot be in. lo and hi are the left and right edges of the region still in play; mid is the middle index $⌊(lo + hi) /2 ⌋$ .

WHY the middle, and why sorted. In a sorted list, everything left of mid is smaller and everything right is bigger. So one comparison at the middle safely rules out a whole half — but only because the order guarantees it. On unsorted data the "throw away a half" logic is a lie.

PICTURE. Searching $7$ in the list $[1, 3, 5, 7, 9, 11]$ . Three shrinking bars: the greyed-out region is the half thrown away; the highlighted region is what survives; the arrow marks mid each round. Round 1 checks the middle value $5$ ; since $5 < 7$ we keep the right half. Round 2 checks $9$ ; since $9 > 7$ we keep the left half. Round 3 lands exactly on $7$ and returns its index $3$ . Read the picture left-to-right, top-to-bottom — every number and decision is drawn on it.

WHY $Θ (lo g n)$ . Its recurrence is $T (n) = T (n /2) + c$ : "the work for $n$ items equals the work for half of them, plus one chunk $c$ (the single middle comparison)." Starting from $n$ and halving repeatedly — $n, \frac{n}{2}, \frac{n}{4}, \dots, 1$ — takes about $lo g_{2} n$ halvings, each costing $c$ . So the total is about $(lo g_{2} n) \cdot c$ → $Θ (lo g n)$ .

Step 8 — The edge cases you must never trip over

WHAT & WHY. Every recursion has quiet corners. Draw them so no reader is ever surprised:

factorial(0) — base case fires immediately, returns $1$ . No dive. (Smallest problem answered directly.)
fib(0) and fib(1) — both base cases; either would recurse below $F_{0}$ if missing.
Binary search, target absent (e.g. $8$ ): the region keeps halving until lo > hi — an empty range. That is the "not found" base case; it returns $- 1$ .
Binary search on an empty list: hi = len(arr)-1 = -1, so lo(0) > hi(-1) is true on the very first call → returns $- 1$ with zero comparisons.

PICTURE. The "target absent" path: lo and hi cross over, leaving no bars highlighted — the moment recursion stops with "not found".

The one-picture summary

All three recursions on one canvas: factorial's straight tower (each step $- 1$ , cost $Θ (n)$ ), Fibonacci's branching tree collapsed by a notebook, and binary search's halving bars (cost $Θ (lo g n)$ ). The three silhouettes — a straight column, a lopsided tree, and shrinking bars — are the whole page in one glance.

Recall Feynman: the whole walkthrough in plain words

Recursion is a stack of paused workers. Factorial: worker $3$ can't finish until worker $2$ finishes, who waits on worker $1$ , who waits on worker $0$ — the only one who knows the answer straight away. Worker $0$ says " $1$ ", and the answer climbs back up, getting multiplied on every floor: $1, 1, 2, 6$ . Fibonacci does the same but each worker calls two helpers, so if nobody writes anything down the same little questions get re-asked a mountain of times — write them in a notebook and the mountain flattens. Binary search is a worker looking in a sorted phone book: open the middle, throw away the half your name isn't in, repeat. Each glance deletes half the book, so you're done in about $lo g_{2} n$ glances. When the book has nothing left to throw away, the name wasn't there.

Connections

Recursion vs Iteration — the tower and halving pictures become loops
Big-O Notation — where $Θ (n)$ , $Θ (φ^{n})$ , $Θ (lo g n)$ come from
Memoization and Dynamic Programming — the notebook in Step 6
Divide and Conquer — binary search is the halving picture
The Call Stack and Stack Frames — the towers in Steps 2–3
Sorting Algorithms — binary search's precondition