Recursion and the Call Stack
A recursive function is a cafeteria plate dispenser running in reverse. Every time the program calls a function, a fresh plate slaps down on top of the pile with the function's name on it, its arguments written on the rim, and a blank space where the answer will go. The plate on top is the one the CPU is staring at. When that function calls another function — or calls itself — a new plate lands on top of the old one and the CPU shifts its attention up. When a function finishes, its plate gets lifted off and the answer it computed gets handed down to the plate underneath, which had been waiting the whole time for that exact number. The pile of plates has a name. It is the call stack, and every running program has one.
Recursion as a programming idea is older than any commercial computer. John McCarthy at MIT designed LISP in 1958 around it — a language where almost every operation was a function calling itself with a smaller problem. McCarthy borrowed the move from mathematics. A mathematician named Stephen Kleene had spent the 1930s formalizing the idea that any computable function could be defined by base cases plus a rule for shrinking the input one notch and asking the same question again. The early FORTRAN compilers did not allow it because the team at IBM thought it would blow up the machine's tiny memory. McCarthy's LISP team kept it in anyway, paid the memory cost, and got back the cleanest way anyone had ever seen to walk a tree or process a list. Every modern language has kept it ever since.
The simplest example is factorial — six times five times four times three times two times one. The rule is one line. Factorial of n is n times factorial of n minus 1, and factorial of 1 is just 1. The base case stops the descent. The recursive case shrinks the problem by one each call.
fn factorial(n: u64, depth: usize) -> u64 {
let pad = " ".repeat(depth);
println!("{pad}calling fact({n})");
let result = if n <= 1 {
println!("{pad}base case fact({n}) = 1");
1
} else {
n * factorial(n - 1, depth + 1)
};
println!("{pad}returning fact({n}) = {result}");
result
}The depth argument is not part of the math. It is a counter the function carries so each line of trace output prints with a little more left-indent than the one above it, which lets you see the stack of plates as text. The real work is the if n <= 1 check and the n * factorial(n - 1, depth + 1) call. When you ask for factorial(6), the function looks at 6, sees it is bigger than 1, and asks for factorial(5) before it can multiply. So it slaps a plate down for the 5 case and waits. The 5 case asks for 4, slaps another plate, waits. The pile grows to six plates deep before any actual multiplying happens.
Now watch the pile build and collapse in the output. The factorial section shows it cleanly.
-- factorial(6): each call waits for the one below --
calling fact(6)
calling fact(5)
calling fact(4)
calling fact(3)
calling fact(2)
calling fact(1)
base case fact(1) = 1
returning fact(1) = 1
returning fact(2) = 2
returning fact(3) = 6
returning fact(4) = 24
returning fact(5) = 120
returning fact(6) = 720
answer: 720
-- fib(15) with memoization --
calling fib(15)
calling fib(14)
calling fib(13)
calling fib(12)
calling fib(11)
calling fib(10)
calling fib(9)
calling fib(8)
calling fib(7)
calling fib(6)
calling fib(5)
calling fib(4)
calling fib(3)
calling fib(2)
calling fib(1)
storing fib(1) = 1
calling fib(0)
storing fib(0) = 0
storing fib(2) = 1
fib(1) cache hit -> 1
storing fib(3) = 2
fib(2) cache hit -> 1
storing fib(4) = 3
fib(3) cache hit -> 2
storing fib(5) = 5
fib(4) cache hit -> 3
storing fib(6) = 8
fib(5) cache hit -> 5
storing fib(7) = 13
fib(6) cache hit -> 8
storing fib(8) = 21
fib(7) cache hit -> 13
storing fib(9) = 34
fib(8) cache hit -> 21
storing fib(10) = 55
fib(9) cache hit -> 34
storing fib(11) = 89
fib(10) cache hit -> 55
storing fib(12) = 144
fib(11) cache hit -> 89
storing fib(13) = 233
fib(12) cache hit -> 144
storing fib(14) = 377
fib(13) cache hit -> 233
storing fib(15) = 610
answer: 610
memo size: 16
-- tower of hanoi, 3 disks A -> C via B --
hanoi(3, A -> C via B)
hanoi(2, A -> B via C)
move disk 1 from A to C
move disk 2 from A to B
move disk 1 from C to B
move disk 3 from A to C
hanoi(2, B -> C via A)
move disk 1 from B to A
move disk 2 from B to C
move disk 1 from A to CRead the factorial block top to bottom. The indent is the depth of the stack. The first six lines push plates: calling fact(6), then calling fact(5) one indent deeper, then calling fact(4), all the way down to calling fact(1). That last call hits the base case — the base case fact(1) = 1 line is the first thing the program can actually compute without asking a deeper call for help. From that point the unwind starts. returning fact(1) = 1 pops the bottom plate, hands the 1 up to the fact(2) plate waiting above it, which can now multiply 2 by 1 and return 2. That 2 goes up to fact(3), which returns 6. The collapse continues until the top plate computes 720 and the pile is empty. The stack grew six deep and shrank back to nothing.
That growing-then-shrinking pattern is the whole story of recursion, and it is also the trap. The second example is the Fibonacci sequence — each number is the sum of the two before it. The naive recursive version would call itself twice for every step, which means the call tree fans out and the same sub-problems get computed thousands of times. The fix is a notebook on the kitchen counter. Before you slap a new plate down for fib(7), you peek at the notebook. If fib(7) is already written there, you copy the answer and skip the call entirely. If not, you do the work, then jot the answer in the notebook before you leave. The technique is called memoization — named by an English researcher named Donald Michie in 1968, from the Latin word for "to be remembered." It turns an exponentially expensive recursion into a linear one.
fn fib(n: u64, memo: &mut HashMap<u64, u64>, depth: usize) -> u64 {
let pad = " ".repeat(depth);
if let Some(&hit) = memo.get(&n) {
println!("{pad}fib({n}) cache hit -> {hit}");
return hit;
}
println!("{pad}calling fib({n})");
let result = if n < 2 {
n
} else {
fib(n - 1, memo, depth + 1) + fib(n - 2, memo, depth + 1)
};
memo.insert(n, result);
println!("{pad}storing fib({n}) = {result}");
result
}The memo argument is the notebook — a HashMap from input to answer that gets passed along on every call. The first thing the function does is check whether n is already in the map. If so, it prints cache hit and returns immediately, no new plate added to the deep part of the pile. If not, it does the real work, stashes the answer with memo.insert, and returns. The output makes the savings visible.
Look at the fib block in the output. The first descent walks straight down from fib(15) to fib(0) — fifteen indented calling fib(n) lines, one plate per level. Once the bottom is reached the unwind begins, and from then on every right-hand call hits the cache. fib(13) asks for fib(12) and fib(11). The fib(12) call has already been computed and stored on the way down, so it returns instantly with fib(12) cache hit -> 144. No new descent. No new plates. The stack never goes deeper than its initial dive. The whole computation finishes with sixteen entries in the memo — one for each of fib(0) through fib(15) — and the answer is 610.
The third example is the puzzle that recursion was invented to handle. Tower of Hanoi is three pegs and a stack of disks of decreasing size on the leftmost peg. You move the whole stack to the rightmost peg, one disk at a time, and a bigger disk can never sit on a smaller one. With three disks the puzzle has seven moves. With sixty-four disks it has 18 quintillion moves, which is why the French mathematician Édouard Lucas, who invented the puzzle in 1883, packaged it with a legend about monks who would not finish until the end of the world. The legend was advertising. The puzzle is real, and it has a four-line recursive solution that is impossible to derive from scratch and obvious once you see it.
fn hanoi(disks: u32, from: char, to: char, via: char, depth: usize) {
let pad = " ".repeat(depth);
if disks == 1 {
println!("{pad}move disk 1 from {from} to {to}");
return;
}
println!("{pad}hanoi({disks}, {from} -> {to} via {via})");
hanoi(disks - 1, from, via, to, depth + 1);
println!("{pad}move disk {disks} from {from} to {to}");
hanoi(disks - 1, via, to, from, depth + 1);
}The trick is the swap. To move n disks from peg from to peg to, you first move the top n - 1 disks out of the way onto peg via, then move the single biggest disk straight from from to to, then move the n - 1 disks from via to to on top of it. The same function calls itself twice with shuffled peg arguments. The base case is one disk, which just moves directly. Run it with three disks and watch the seven moves spill out.
The hanoi block in the output shows the recursion tree flattened. The outer hanoi(3, A -> C via B) plate sits at the top of the pile. It calls hanoi(2, A -> B via C) first, which calls hanoi(1, A -> C via B), which is the base case and prints the move directly. The pile peaks at three plates deep — depth equals the number of disks. Each disk doubles the work, which is why sixty-four disks is hopeless and three is fine.
There is one thing the call stack cannot do, and it is the reason Rust forces you to think about recursion harder than higher-level languages do. The stack is a fixed-size region of memory the operating system hands your thread when it starts — about 8 megabytes on a default Linux or macOS process, often a single megabyte on a worker thread. Every plate takes some bytes. If a recursive function descends thousands of calls deep, the pile crashes through the ceiling and the program dies with a stack overflow. Some languages — Scheme, Haskell, the ML family — hide this by rewriting certain recursive functions into loops at compile time, a trick called tail-call optimization. Rust does not guarantee it. The compiler may sometimes do it, but you cannot rely on it. For unbounded depth you give up the recursive form and rewrite the function as a while loop that pushes work items onto a Vec you manage by hand. The Vec is your own private call stack on the heap, which can grow as far as the heap allows.
That heap-backed stack is the bridge to the next idea — when one recursive shape stops being natural to walk by recursion and starts to need an explicit stack, you are ready for the data structures the algorithm chapter spends the rest of its time on.