Recursion & the Call Stack

Recursion and Bits · 35 min

Data structures & algorithms · Foundations

Recursion & the call stack

Two questions build any recursive function. This page traces factorial(4) frame by frame, so you watch the stack grow on the way down and hand the answer back on the way up.

Push and pop the stack yourself →
Push · 4 frames go down
→
Pop · 24 comes back up

01 The idea

A function that calls itself, and a stack that remembers

Some problems are defined in terms of themselves. Four factorial is four times three factorial. The size of a folder is the size of everything inside it, and the things inside it are folders. When the definition points back at itself, the code can too: the function calls itself on a smaller input and uses whatever comes back.

What makes that work is not magic. Every call that has not finished yet is parked in a box called a stack frame, and the runtime keeps those boxes stacked in order until the answers arrive.

Ask two questions. Which input can I answer with no further call? That is the base case. How do I build the answer for n out of the answer for something smaller? That is the recursive case. Every call that cannot answer yet waits on the stack until the answer comes back up.
Base caseThe input the function answers outright, with no call to itself. Without a base case that every input can reach, the calls never stop.
Recursive caseThe input the function cannot answer directly. It calls itself on a smaller input and uses that result. The input has to move toward the base case, every time.
Stack frameThe box the runtime creates for one call, holding that call's parameters and the exact spot it must resume at. Frames pile up going down and pop off coming back up.

02 Hand trace

factorial(4), one frame at a time

Take factorial(4), defined the way a maths book defines it: 4! = 4 × 3!. Each box below is one stack frame, and the newest frame sits at the right-hand end. Follow n down and the returned value back up. A rose note means that frame still owes an answer; a green note means it has one.

push n=44parks at 4 × factorial(3) — no answer yet
push n=343parks at 3 × factorial(2) — still nothing
push n=2432parks at 2 × factorial(1) — three frames owing
push n=14321n = 1 is the base case — returns 1
pop n=143→2factorial(2) wakes up: 2 × 1 = 2
pop n=24→6factorial(3) wakes up: 3 × 2 = 6
pop n=3→24factorial(4) wakes up: 4 × 6 = 24

Read the two halves separately. The top four rows are the descent: four frames created and not one multiplication done. The first three park mid-expression; the fourth, n = 1, is the base case, so it answers outright and turns the run around. The bottom three rows are the unwind, and that is where all three multiplications happen, in the reverse order of the calls. One more pop — factorial(4) itself — empties the stack, and 24 is the answer. Most students follow the descent and lose the unwind, and the unwind is where the answer is actually built.

03 Code

The two-question method, written down

The trace showed a shape you can now write as code. Every recursive function is the same two-part answer to the two questions from section 01, and getting either part slightly wrong is exactly how a stack fills up.

Broken · no base case

function factorial(n):    return n * factorial(n - 1)   # nothing stops it # 4 -> 3 -> 2 -> 1 -> 0 -> -1 -> -2 ...# frames pile up until the stack overflows

Correct · base case first

function factorial(n):    if n <= 1:                    # 1 · base case        return 1    return n * factorial(n - 1)   # 2 · recursive case# factorial(4) = 24, four frames deep

The base case goes first. The left version has no stopping condition, so factorial(4) calls 3, then 2, then 1, then 0, then −1, and keeps going. Nothing returns, so nothing pops, and the runtime raises a stack overflow once the frames fill the stack.

Write n <= 1, not n == 1. The <= form catches 0 as well as 1. With n == 1, a call to factorial(0) slides straight past the check and heads off toward −1. A base case that some inputs step over is the same bug as having no base case at all.

The multiply is what the frame is holding. n * factorial(n - 1) cannot be computed when the call is made, because the right-hand side is not a number yet. The frame stores n and parks at the multiply. That parked multiply is why the answer is assembled on the way back up, and why n frames of memory are the price of writing it this way.

05 Cheat sheet

What gets asked about recursion

Recursion shapeCalls for input nDeepest stack
Linear · one call per level (factorial)O(n)O(n)
Tree · two calls per level (naive fib)O(2ⁿ)O(n)
Halving · one call on half the inputO(log n)O(log n)
Base case unreachablenever endsoverflows
Depth is the memory billOne frame per pending call, and every frame is real memory. The default limit in Python is 1000 frames; a JVM thread usually manages a few thousand before a StackOverflowError.
Depth and calls are different numbersfactorial(4) and fib(4) both stack 4 frames deep, but factorial makes 4 calls and fib makes 9. Depth costs you memory; calls cost you time.
Every recursion has a loop twinAnything recursive can be rewritten with your own stack on the heap. You do that when the depth would outgrow the runtime stack, not when you want speed.

06 Where & why

When recursion earns its frames

Recursion is not faster than a loop. It costs a frame per pending call and it can overflow where a loop cannot. What you buy is code shaped like the data, and on self-similar data that shape removes most of the bookkeeping bugs.

Reach for it when…

The data is self-similarA folder holds folders, a tree node holds nodes, a JSON value holds JSON values. The code for the whole is the code for the part.
The definition is already recursiveThe spec says the answer for n uses the answer for n − 1. Write it the way it reads and there is nothing to translate.
You need to undo a choiceBacktracking — N-Queens, sudoku, permutations — gets its undo free: when the frame pops, everything it held disappears with it.
The depth is bounded and smallA balanced tree of a million nodes is only about 20 levels deep, so the stack never gets near its limit.

Use something else when…

SituationBetter choiceWhy
Depth grows with the input — a linked list of 100,000 nodesA loop, or your own stack on the heapThe runtime stack holds a few thousand frames. A stack you build on the heap holds millions.
The same sub-problem is solved again and again — naive fibMemoisation, or a bottom-up loopEach value is then computed once instead of thousands of times, turning O(2ⁿ) into O(n).
The recursion is a straight sweep — sum a list, reverse a stringA for loopSame time, O(1) stack instead of O(n), and no overflow to worry about.
You will never ship recursive factorial. You will write recursion over trees, files and grids constantly, and you will still be asked factorial in an interview — because it is the smallest problem that shows whether you can name the base case and describe the unwind.

07 Interview questions

Say these out loud

The unwind question is the one that separates people who have read about recursion from people who have traced it.

What is recursion?
A function that solves a problem by calling itself on a smaller version of the same problem. It needs at least one input it can answer outright — the base case — or the calls never stop. Everything else is the recursive case, which shrinks the input and uses the answer that comes back.
What are the two questions you ask before writing a recursive function?
First: which input can I answer with no further call? That is the base case. Second: how do I build the answer for n from the answer for something smaller? That is the recursive case. If the second one does not move strictly toward the first, the function never terminates.
What actually happens in memory when a function calls itself?
Each call gets its own stack frame holding that call's parameters, its local variables and the address to resume at once the call below returns. factorial(4) puts four frames on the stack before any of them finishes. They pop in reverse order, so the last frame created is the first to return.
Walk me through factorial(4).
Four frames go down: factorial(4) parks at 4 × factorial(3), and so on until factorial(1) hits the base case and returns 1. Then it unwinds: factorial(2) computes 2 × 1 = 2, factorial(3) computes 3 × 2 = 6, factorial(4) computes 4 × 6 = 24. Nothing is multiplied on the way down.
Why does no multiplication happen on the way down?
Because n * factorial(n - 1) cannot be evaluated until factorial(n - 1) hands back a number. The frame stores n, makes the call and parks at the multiply. That parked state is exactly what a stack frame is for, and it is why the memory cost grows with the depth.
What causes a stack overflow?
Frames that get pushed and never popped. The usual causes are a missing base case, a base case the input can step over such as n == 1 called with 0, or a recursive case that does not shrink the input. The stack is a fixed region, so once the frames fill it the runtime raises an error. Python stops you earlier, at a recursion limit of 1000 by default.
What is the time and space complexity of recursive factorial?
O(n) time, because there is one call per value from n down to 1 and each does constant work. O(n) space, because n frames are alive at the deepest moment. The loop version is also O(n) time but O(1) space, and that space gap is the honest cost of writing it recursively.
How do you work out how deep a recursion will go?
Count the longest chain of calls from the first call down to a base case, not the total number of calls. factorial(4) and fib(4) both reach depth 4, but factorial makes 4 calls and fib makes 9. Depth sets the memory cost; the call count sets the time cost.
Why is naive fib(n) exponential when factorial(n) is only linear?
factorial makes one call per level, so the calls form a line of length n. fib makes two calls per level, so the calls form a branching tree instead of a line. fib(4) already costs 9 calls against factorial's 4, and fib(30) costs 2,692,537, because the same sub-problems are recomputed over and over. The exact count is 2 × fib(n + 1) − 1, so it multiplies by about 1.6 per level rather than a full 2 — O(2ⁿ) is the usual, deliberately loose, upper bound. A cache collapses it back to linear.
What is tail recursion, and does it help?
A call is tail recursive when the recursive call is the last thing the function does, with no pending work waiting on its result. A compiler can then reuse the same frame instead of pushing a new one, which turns the recursion into a loop. Note that return n * factorial(n - 1) is not tail recursive, because the multiply is still pending. Scheme and Scala optimise tail calls and C compilers often do at higher optimisation levels, but CPython and the JVM do not.
Recursion or iteration — which do you actually reach for?
Iteration for a plain sweep over a sequence: it is faster, uses no stack and cannot overflow. Recursion when the data is self-similar — trees, nested directories, JSON, backtracking — where the recursive version is shorter and much harder to get wrong. Nobody ships recursive factorial; interviewers ask it because it is the smallest example that shows whether you understand the base case and the unwind.

08 Practice problems

Base case first, every time

For each one, write the base case before the recursive call. Then check that the recursive case actually reaches it from every legal input.

Sum to n

Easy
Write sumTo(n) that returns 1 + 2 + … + n using recursion and no loop.
Follow-up
Stopping at sumTo(1) looks like the natural choice, but then a call with n = 0 walks straight past the check and heads off into negative numbers — decide whether n = 0 is a legal input before you pick.
Show the hint
Write the base case first and ask what the sum of no numbers should be.

Count frames and calls

Easy
Without running anything, state the total number of calls and the deepest stack for factorial(6) and for fib(5).
Follow-up
The two numbers match for factorial and differ for fib, so you have to count the nodes of the call tree and its longest root-to-leaf path separately.
Show the hint
Depth is the longest path down to a base case; calls are every node in the tree, and fib branches into two children at every non-base node.

Reverse a string

Medium
Write reverse(s) that returns the reversed string by taking the first character off, recursing on the rest, and putting that character at the end.
Follow-up
Two base cases look reasonable — the empty string and a one-character string — but one of them leaves a legal input with nothing to stop it.
Show the hint
If each call removes exactly one character, ask which candidate a string of length 0 can ever match.

Print on both phases

Medium
Write countdown(n) so that countdown(3) prints 3 2 1 1 2 3, using one recursive call and two print statements.
Follow-up
The two 1s in the middle are a single frame printing twice, so the base case itself must print nothing — stop at n = 1 with a print and you get 3 2 1 2 3 instead.
Show the hint
A statement before the recursive call runs on the way down; a statement after it runs on the way back up.

Fix the broken base case

Medium
Given power(b, e) written as if e == 1: return b followed by return b * power(b, e - 1), say exactly what power(2, 0) does and rewrite it so every exponent from 0 upward works.
Follow-up
Changing == to <= is not enough, because power(2, 0) has to come back with 1, so the value the base case returns changes too.
Show the hint
Ask what the answer should be when the exponent is 0, then make that the base case.

Count the calls without running it

Hard
For the naive fib in the console, work out a recurrence for calls(n) — the total number of calls fib(n) makes — and use it to explain why fib(50) is hopeless while factorial(50) is instant.
Follow-up
You are not counting a loop: the count itself obeys a Fibonacci-shaped recurrence, so you end up solving a recursion about a recursion.
Show the hint
Get calls(0), calls(1) and calls(2) by hand from the call tree, then line the sequence up against the Fibonacci numbers themselves.