Recursion and Hashing

Recursion and the call stack

A function that calls itself, and where it lives

~12 minLesson 7 of 25Written by Claude Opus 4.8

A function that calls itself on a smaller input until a base case stops it - and the invisible stack of paused calls that makes the whole trick work.

Recursion is a function that solves a big problem by calling itself on a smaller version of the same problem - trusting that the smaller call will succeed - until the problem is so small there is nothing left to reduce. That last, un-reducible case is the base case. Miss it, and the function calls itself forever. Get it right, and problems that look tangled unfold into two short lines.

Two cases, always

Every recursive function is a fork. The base case is the smallest input you can answer outright, with no further calls - the floor. The recursive case reduces the input a little and calls itself, betting that the smaller call returns the right answer. Reduce toward the base, or you never stop.

The call stack: where paused calls wait

When $fib (5)$ calls $fib (4)$ , the outer call does not vanish - it pauses, mid-expression, waiting for an answer. The machine remembers each paused call as a stack frame: a small record holding that call's arguments and the exact spot to resume. Frames stack up like plates: the newest call sits on top, and only the top call runs. When a call returns, its frame is popped and its value handed down to the call underneath, which resumes. Push on the way down, pop on the way up.

That stack is finite. A recursion with no reachable base case (or one that recurses on the same input) never pops - frames pile up until the machine runs out of room and crashes with a stack overflow. The base case is not decoration; it is what lets the stack drain.

Watch the stack breathe

Below is $fib (5)$ - Fibonacci, where $fib (n) = fib (n - 1) + fib (n - 2)$ . Step through with Next (or hit Play). Frames push onto the call stack on the way down; as each call resolves, its frame pops and its value flows back up the tree, turning nodes green. Then flip on Memoize and watch the greyed-out branches - the repeated work - disappear.

Recursion visualizer - fib(5)

Step through the tree, toggle memoize, or play. Frames push on the way down and pop on the way up.

Memoize (cache results)calls: 1 / 15

Recursion tree - the number inside each node is its argument

Call stack

fib(5)

Call fib(5). Since n ≥ 2 we need fib(4) + fib(3). Push a frame and recurse left first.

running (top of stack)paused on the stackreturned a valuecache hitpruned by memo

The exponential you can see

Naive

fib (5)

makes 15 calls - and most are duplicates.

fib (3)

gets computed twice,

fib (2)

three times. Push

n

higher and the tree doubles at every level:

fib (30)

is over a million calls. Memoization stores each answer the first time and returns it instantly ever after - the second

fib (3)

becomes a one-step cache hit, and its whole subtree (greyed out in the demo) is never built. That drops

fib (5)

from 15 calls to 9, and turns exponential into linear.

Counting the calls

Let $C (n)$ be the number of calls naive fib makes. Every non-base call spawns two more, plus itself:

C (n) = C (n - 1) + C (n - 2) + 1 \sim O (φ^{n}) \approx O (1.61 8^{n}) .

That is the same golden ratio $φ$ the Fibonacci numbers themselves grow by - the cost is the sequence. Memoization computes each $fib (k)$ exactly once, so it runs in $O (n)$ . Factorial is gentler: $n! = n \cdot (n - 1)!$ with base $0! = 1$ recurses in a single straight line, $n$ frames deep, at $O (n)$ - no branching, nothing to memoize.

In code

Both patterns are two-liners once you spot the base case. Notice fib_memo differs by exactly one idea: check the cache before recursing, fill it after.

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

def fib(n):                            # naive - O(1.618ⁿ), exponential
    if n < 2:
        return n                        # fib(0)=0, fib(1)=1
    return fib(n - 1) + fib(n - 2)      # two recursive calls

def fib_memo(n, cache):               # memoized - O(n), linear
    if n < 2:
        return n
    if n in cache:                     # seen it? return instantly
        return cache[n]
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]                    # store once, reuse forever

Factorial recurses in a straight line; naive fib branches; fib_memo caches.

Three ways recursion bites

1. No base case (or one you never reach) → frames pile up → stack overflow. 2. Not shrinking - fib(n) calling fib(n) loops forever; each call must move toward the base. 3. Deep-but-valid recursion still has a ceiling: Python caps at ~1000 frames by default, so a linear recursion over a million items overflows even though it is "correct." When depth is the enemy, rewrite as a loop.

Check yourself

What stops a correctly written recursive function from running forever?

Why does naive fib(n) explode while the memoized version stays cheap?

Recall: when a recursive call is made, what exactly gets pushed onto the call stack - and when is it popped?

Try to state it, then check.

Primary source

Harvard's CS50x devotes a full lecture to recursion and the stack - its stack-frame diagrams are the clearest intro anywhere. For the memoization angle and the friendliest recursion illustrations in print, see the recursion chapter of Grokking Algorithms (2nd ed.).

Ask your teacher

Want to know how the machine turns recursion into a real loop (tail-call optimization), or why some languages do not? Ask me. And here is the payoff for the LLM path: recursion + a base case is exactly how a language model writes text. It generates one token, feeds that token back as input, and calls itself again - autoregression - until it emits an end-of-sequence token, the base case. Even memoization returns: the model caches the work it already did for earlier tokens as the KV cache, so it never recomputes them. Same two ideas, all the way up.

Lock it in

A recursive function is a fork: a base case that returns without recursing, and a recursive case that shrinks the input toward that base.
Each paused call is a stack frame pushed on the way down and popped on the way up; no reachable base case means the stack never drains and overflows.
Naive fib is O(1.618ⁿ) because it rebuilds duplicate subtrees; memoization caches each answer once and collapses it to O(n).
Even valid deep recursion has a frame ceiling (~1000 in Python); when depth is the enemy, rewrite it as a loop.