Recursion & Mathematical Induction
Recursion is a function that calls itself on a smaller version of its own problem. Induction is a proof that works the same way: show the claim for the smallest case, show that each case follows from the one before, conclude it holds for all. They are not merely similar. They are the same idea seen from two sides, and once you see that, every recursive algorithm comes with its own correctness proof for free, and every proof tells you how to write the algorithm.
Why this exists
Trees, graphs, divide and conquer, backtracking and dynamic programming are all recursion in different clothing. A binary tree is defined recursively (a node with two subtrees that are themselves binary trees), so almost every algorithm on it is naturally recursive. Merge sort and quicksort recurse on halves. Backtracking recurses on partial solutions. Dynamic programming is recursion with the repeated subproblems remembered. Six of the thirteen modules in this course would not exist without it.
The idea is older than computers. Dedekind used recursive definitions of arithmetic in 1888; Gödel's 1931 incompleteness paper made "recursive function" a technical term; Church's lambda calculus (1936) and Kleene's work defined computability itself in terms of recursion. In programming, Lisp (McCarthy, 1958) made recursion the primary control structure, and Dijkstra's 1960 ALGOL 60 compiler was the first to implement recursive procedures with a run-time stack, the mechanism every language uses today. Mathematical induction is older still: implicit in Euclid, explicit in Pascal's 1665 treatise on the arithmetic triangle, and formalised as the fifth of Peano's axioms in 1889.
This lesson does four things. It explains what the machine does when a function calls itself, so that stack depth and stack overflow stop being mysteries. It makes the recursion-induction correspondence precise and uses it to prove three real algorithms correct. It teaches loop invariants, induction's form for iterative code. And it shows how to turn recursion into iteration when the stack is the problem.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| A structure defined in terms of itself: tree, nested list, JSON, file system, expression | Structural recursion: one case per constructor. |
| "Do the same thing to each half" / "split and combine" | Divide and conquer; recurrence . |
| "All combinations / permutations / subsets / arrangements that satisfy…" | Backtracking: recurse on a partial solution, undo on return. |
| "Number of ways to…", "minimum cost to…", a choice at each step with overlapping subproblems | Recursion first, then memoise it: dynamic programming. |
x^n, fib(n), matrix powers, with up to | Fast exponentiation by halving . |
| A linked list operation phrased as "the rest of the list" | Recursion on the tail, but check the depth limit. |
| Parsing an expression with nested parentheses | Mutual recursion: expr calls term calls factor calls expr. |
| "Prove this algorithm is correct" | Induction on input size for recursion; a loop invariant for iteration. |
| Recursion depth could exceed about (long lists, deep trees, big ) | Convert to iteration with an explicit stack, or raise the limit and know the risk. |
| An exponential-time recursive solution that repeats work | Draw the recursion tree, find the repeated subtrees, memoise. |
Intuition & first principles
The leap of faith
Here is factorial, the canonical first recursive function:
# fragment — definition
def factorial(n):
if n == 0:
return 1 # base case
return n * factorial(n - 1) # recursive case: smaller argument
To write it you did not think about the whole chain of calls. You thought: "if someone hands me a correct answer for , I can produce the answer for by multiplying by ." Then you handled the one case where nobody can hand you anything smaller. That is the entire method. Trusting that the recursive call returns the right answer is sometimes called the recursive leap of faith; it is not faith at all, it is the inductive hypothesis, and the next section makes that precise.
Every correct recursive function has two properties:
- A base case (or several): inputs for which the answer is returned directly, without a recursive call.
- A progress measure: some non-negative integer quantity of the input that is strictly smaller in every recursive call than in the current call. For factorial it is itself. For binary search it is the size of the range. For a tree traversal it is the size (or height) of the subtree. For backtracking it is the number of positions left to fill.
A progress measure guarantees termination: a strictly decreasing sequence of non-negative integers must reach the base case in finitely many steps. If you cannot name the progress measure, you do not yet know whether your function terminates.
Head recursion, tail recursion and the stack
In n * factorial(n - 1) the recursive call happens first and the multiplication happens after it returns; the frame for factorial(n) must stay alive, holding n, until factorial(n-1) is done. This is head recursion (work after the call). In
# fragment — accumulator form
def factorial_acc(n, acc=1):
if n == 0:
return acc
return factorial_acc(n - 1, acc * n)
the recursive call is the last thing the function does and its result is returned unchanged. This is tail recursion. The frame for factorial_acc(n, acc) has nothing left to do once the call is made, so in principle it could be discarded before the call rather than after. Some compilers do exactly that (tail-call elimination), which turns the recursion into a loop with constant stack. Most of the languages in this course do not; the section on converting recursion to iteration says which and why.
Mechanics: what the machine does
Frames, return addresses and the call stack
Each function call creates a stack frame (also activation record): a block of memory holding the function's parameters, its local variables, and the return address, the point in the caller's code to resume when this call returns. Frames live on the call stack, a region of memory that grows with each call and shrinks with each return. The hardware helps: the call instruction pushes the return address, ret pops it, and a register (the stack pointer) marks the top.
Here is the stack at its deepest while computing factorial(4), just after factorial(0) has been called and before it returns. Five frames are alive; the bottom one is the caller's.
flowchart TD
F0["factorial(0)<br/>n = 0 → returns 1<br/>return to: multiply in factorial(1)"]
F1["factorial(1)<br/>n = 1, waiting for factorial(0)<br/>return to: multiply in factorial(2)"]
F2["factorial(2)<br/>n = 2, waiting for factorial(1)<br/>return to: multiply in factorial(3)"]
F3["factorial(3)<br/>n = 3, waiting for factorial(2)<br/>return to: multiply in factorial(4)"]
F4["factorial(4)<br/>n = 4, waiting for factorial(3)<br/>return to: caller"]
M["main<br/>calls factorial(4)"]
F0 --> F1 --> F2 --> F3 --> F4 --> M
style F0 fill:#ef6c00,color:#fff
The top frame (factorial(0)) returns 1; its frame is popped and execution resumes at the multiply in factorial(1), which computes and returns; factorial(2) computes ; factorial(3) computes ; factorial(4) computes and returns to main. The unwinding happens in the reverse order of the calls: last in, first out. That is why it is a stack.
Two consequences follow directly. Recursion depth costs memory: nested calls need frames, so a recursive function with depth uses auxiliary space even if it allocates nothing else. The stack is finite: when the frames exceed the stack's size, the program fails with a stack overflow, which each language reports differently.
Stack limits per language
The limits below are typical defaults; the exact depth you reach depends on the frame size (number of locals and parameters), the JIT or optimiser, and the platform. Treat them as orders of magnitude, and measure your own environment before relying on them.
| Language | Default limit | What happens | How to change it |
|---|---|---|---|
| Python (CPython) | sys.getrecursionlimit() is 1000 frames by default (verified on Python 3.14). | RecursionError: maximum recursion depth exceeded. | sys.setrecursionlimit(10**6); since 3.12 pure-Python frames do not consume the C stack, so large limits are safer than they were, but C-level recursion (e.g. in json, pickle) has its own separate limit. Threads created with threading.stack_size(...) can get a bigger C stack. |
| Java (HotSpot) | Thread stack typically 512 KB to 1 MB (-Xss default is 1 MB on 64-bit Linux and Windows). Depth depends on frame size: a tiny frame allows on the order of to a few calls; on the authoring machine (Java 21, default -Xss) a one-int frame reached about 18,000. | java.lang.StackOverflowError. | -Xss16m on the command line, or run the work in new Thread(null, runnable, "name", 1L << 28) with an explicit stack size. |
| C++ | Main-thread stack is set by the OS: 8 MB default on Linux (ulimit -s), 1 MB on Windows (MSVC default), 8 MB on macOS. Depth is stack size divided by frame size: roughly calls for a 64-byte frame on Linux. | Segmentation fault / access violation, no exception. | Linker flag (/STACK:268435456 on MSVC, -Wl,-z,stacksize=... or ulimit -s unlimited on Linux), or run in a std::thread created via a native API with a larger stack. Competitive judges often give 256 MB. |
| JavaScript (Node, V8) | About 984 KB of stack by default, which is on the order of simple frames (about 9,600 for a trivial one-argument function on the authoring machine, Node 24; --stack-size is in KB). | RangeError: Maximum call stack size exceeded. | node --stack-size=65500 script.js; values much above the OS thread stack can crash the process instead of throwing. |
The practical rule: recursion depth above a few thousand needs a plan. Either the input is bounded (balanced trees have depth , which is at most about 60 for any input that fits in memory), or you raise the limit deliberately, or you rewrite with an explicit stack. Recursive DFS over a graph with vertices in Python will crash on a path graph; that is the most common recursion bug in contest code.
Trace table: fast exponentiation of
The canonical recursive algorithm that is not a toy. Fast exponentiation computes with multiplications instead of :
Progress measure: , which at least halves every call. Depth: calls including the base case; for that is 5. The trace below is the recursive version in the implementation section, computed by script. Reading it top to bottom follows the calls down; reading the result column bottom to top follows the returns up.
| Call depth | Call | parity | half returned by the call below | Result returned |
|---|---|---|---|---|
| 0 | power(3, 13) | odd | 729 | |
| 1 | power(3, 6) | even | 27 | |
| 2 | power(3, 3) | odd | 3 | |
| 3 | power(3, 1) | odd | 1 | |
| 4 | power(3, 0) | base case | — |
Five calls, five multiplications (counting the squarings), against twelve for the naive loop. For it is about 60 calls against iterations; this is why modular exponentiation in RSA and Diffie–Hellman is feasible at all (Cryptography for Engineers).
The iterative version in the implementation section walks the bits of from least significant upward, maintaining result and the current power x. For :
| Iteration | (binary) | low bit | result after | x after (squared) |
|---|---|---|---|---|
| 1 | 1101 | 1 | 9 | |
| 2 | 110 | 0 | 3 | 81 |
| 3 | 11 | 1 | 6561 | |
| 4 | 1 | 1 | 43,046,721 |
Same answer, no stack. The two versions compute the same product in a different association; the correctness of each is a separate small induction, which the next section does for the recursive one.
Recursion is induction, induction is recursion
The correspondence
Mathematical induction proves a statement for all natural numbers in two steps:
- Base step: prove (or , or whichever smallest case applies).
- Inductive step: prove that for every , implies . The assumption is the inductive hypothesis.
Strong induction lets the inductive step assume for all , not just . It is equivalent to ordinary induction but matches recursion that calls itself on or on several smaller arguments.
Now lay a recursive function alongside it:
flowchart LR
subgraph REC["Recursive function"]
B1["Base case:<br/>return answer directly"]
R1["Recursive case:<br/>call self on smaller input,<br/>combine"]
P1["Progress measure<br/>strictly decreases"]
end
subgraph IND["Induction proof"]
B2["Base step:<br/>prove P(smallest)"]
R2["Inductive step:<br/>assume P(smaller),<br/>prove P(this)"]
P2["Well-ordering:<br/>no infinite descent"]
end
B1 <--> B2
R1 <--> R2
P1 <--> P2
The base case of the function is the base step of the proof. The recursive call is where you use the inductive hypothesis: "the call on the smaller input returns the correct answer". The combining step is where you prove the inductive step: "given correct answers for the smaller inputs, this combination is the correct answer for the current input". The progress measure is what makes the induction well-founded. When you write a recursive function by thinking "assume the recursive call works", you are doing the inductive step in your head; writing the proof down just makes it explicit.
The same correspondence runs the other way. Every induction proof is a recursive algorithm for constructing the object or the certificate: a proof that every tree with nodes has edges tells you how to count edges recursively.
Proof 1: the sum of the first integers
Claim. For all , .
Base step. : the empty sum is , and .
Inductive step. Assume for some . Then
which is the claim for .
The corresponding recursive function is sum_to(n) = 0 if n == 0 else sum_to(n-1) + n, and the proof is exactly its correctness proof: base case returns the right value; recursive case returns (correct answer for ) , which is the correct answer for . The closed form is what the complexity lesson used for the triangle loop.
Proof 2: correctness of recursive binary search
# fragment — recursive binary search
def bsearch(a, lo, hi, t):
"""a[lo..hi] is sorted. Return an index i in [lo, hi] with a[i] == t, or -1."""
if lo > hi:
return -1
mid = (lo + hi) // 2
if a[mid] == t:
return mid
if a[mid] < t:
return bsearch(a, mid + 1, hi, t)
return bsearch(a, lo, mid - 1, t)
Claim. For a sorted array a and any lo, hi, t: bsearch(a, lo, hi, t) returns an index with if such an index exists, and otherwise.
Proof by strong induction on the range size .
Base step (, i.e. lo > hi). The range is empty, so no such index exists, and the function returns .
Inductive step (). Assume the claim for all ranges of size less than . Since lo <= hi, mid = (lo + hi) // 2 satisfies , so a[mid] is a valid read. Three cases.
- : the function returns
mid, which is in range and holds . - : because
ais sorted, for every , so no index in holds ; any valid index must lie in . That range has size , so by the inductive hypothesis the recursive call returns a valid index in it if one exists and otherwise. Either way it is the correct answer for . - : symmetric, with the range of size .
Termination. The progress measure is , which strictly decreases in both recursive calls because is inside and is excluded from the sub-range.
Notice what the proof caught: the step " so the sub-range is strictly smaller" is exactly the place where writing bsearch(a, mid, hi, t) instead of mid + 1 would break the proof, and that is the infinite-loop bug people actually write. Module 2's binary-search lesson builds on this template for every variant (first occurrence, last occurrence, binary search on the answer).
Proof 3: correctness of merge
# fragment — recursive merge of two sorted lists
def merge(a, b):
if not a: return b
if not b: return a
if a[0] <= b[0]:
return [a[0]] + merge(a[1:], b)
return [b[0]] + merge(a, b[1:])
Claim. For sorted lists a and b, merge(a, b) returns a sorted list containing exactly the elements of a and b (as a multiset).
Proof by strong induction on .
Base step. If either list is empty, the other is returned. It is sorted (given) and is exactly the union.
Inductive step. Both non-empty; suppose (the other case is symmetric). Since a is sorted, for all ; and for all since b is sorted. So is a minimum of the combined multiset. The recursive call merge(a[1:], b) has total size , so by the inductive hypothesis it returns the sorted union of a[1:] and b. Prepending , which is every element of that union, yields a sorted list, and its contents are exactly a[1:] ∪ b ∪ = a ∪ b.
Termination. decreases by one per call.
Merge sort's full proof is one more layer of the same induction: assume the two recursive sorts are correct (inductive hypothesis on the half-size inputs), then merge is correct by Proof 3, so the whole is correct. Module 2 does that layer.
Structural induction on lists and trees
Induction on a natural number is a special case. Structural induction proves a property of every value of a recursively defined type by proving it for each constructor of the type, assuming it for the constructor's recursive components.
A list is either empty (nil) or an element followed by a list (x :: xs). To prove for all lists: prove , and prove that implies for every .
Example. length(reverse(xs)) == length(xs), where reverse(nil) = nil and reverse(x :: xs) = reverse(xs) ++ [x]. Base: both sides are 0. Step: length(reverse(x :: xs)) = length(reverse(xs) ++ [x]) = length(reverse(xs)) + 1 = length(xs) + 1 = length(x :: xs), using the hypothesis in the third equality.
A binary tree is either empty or a node with a value, a left subtree and a right subtree. To prove for all binary trees: prove , and prove that and imply .
Example. A binary tree of height has at most nodes, with the empty tree having height . Base: the empty tree has nodes. Step: a node with subtrees , of heights has, by hypothesis, at most nodes. Inverting, a tree with nodes has height at least , which is the lower bound that makes balanced trees in Module 3.
The code shape follows the proof shape exactly: a recursive function on a tree has an if root is None branch (the base constructor) and a branch that calls itself on root.left and root.right (the recursive constructor). The depth_rec function in the implementation section is one; its correctness proof is three lines of structural induction.
Loop invariants: induction for loops
A loop is recursion with the frames flattened, and its correctness proof is induction over iterations. A loop invariant is a statement about the program state that is true at the start of every iteration. Proving a loop correct has three parts, which CLRS names:
- Initialization. The invariant holds before the first iteration.
- Maintenance. If it holds before an iteration, it holds before the next.
- Termination. When the loop exits, the invariant together with the exit condition gives you the property you wanted. (And the loop does exit: a progress measure, again.)
Initialization is the base step, maintenance is the inductive step, and termination is where you cash the proof in.
Worked proof: insertion sort
# fragment — insertion sort
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
Invariant (outer loop). At the start of the iteration with index , the subarray a[0..i-1] consists of the elements originally in a[0..i-1], in sorted order.
Initialization. : a[0..0] is one element, trivially sorted and trivially the original contents.
Maintenance. Assume the invariant at the start of iteration . The inner while shifts each a[j] > key one position right, scanning from downward, and stops at the first with a[j] <= key (or at ). Its own invariant: a[j+2..i] holds the elements of the original a[j+1..i-1], all greater than key, each shifted right by one; a[0..j] is untouched and sorted. When it stops, key is written to a[j+1], which is after everything key and before everything key. So a[0..i] is sorted and contains the original a[0..i]. That is the invariant for .
Termination. The outer loop exits with . The invariant says a[0..n-1], the whole array, is sorted and is a permutation of the original. The loop exits because increases by one each iteration; the inner loop exits because decreases by one and is bounded below by .
Worked proof: two-pointer pair sum on a sorted array
# fragment — two pointers
def pair_sum(a, t):
"""a sorted ascending. Return (i, j) with i < j and a[i] + a[j] == t, or None."""
lo, hi = 0, len(a) - 1
while lo < hi:
s = a[lo] + a[hi]
if s == t:
return (lo, hi)
if s < t:
lo += 1
else:
hi -= 1
return None
Invariant. At the start of each iteration: if any pair with and exists in the array, then some such pair satisfies . (Informally: no solution has been discarded.)
Initialization. , : every pair is inside the range.
Maintenance. Suppose the invariant holds and the loop body runs with .
- If : for every , sortedness gives . So no pair that uses index with a partner in sums to . Discarding (setting ) therefore discards no solution pair inside the range; if a solution existed in it still exists in .
- If : for every , . No pair using works; discard .
Termination. decreases by one each iteration, so the loop ends. If it returned , that is a valid pair by the s == t check. If it exited with , the range contains no pair , so by the invariant no solution exists anywhere, and returning None is correct.
That proof is the whole content of the two-pointer technique, and Two Pointers in Module 1 reuses the argument for every variant. The exchange "if then cannot be in any solution with a partner in range" is the step candidates most often cannot explain in interviews; now you can.
The ladder: Fibonacci, from exponential to logarithmic
Fibonacci is the standard example of recursion done badly and then well, and it previews Module 6.
Rung 1: naive recursion,
# fragment — naive
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
Draw the recursion tree for fib(5):
flowchart TD
A["fib(5)"] --> B["fib(4)"]
A --> C["fib(3)"]
B --> D["fib(3)"]
B --> E["fib(2)"]
C --> F["fib(2)"]
C --> G["fib(1)"]
D --> H["fib(2)"]
D --> I["fib(1)"]
E --> J["fib(1)"]
E --> K["fib(0)"]
F --> L["fib(1)"]
F --> M["fib(0)"]
H --> N["fib(1)"]
H --> O["fib(0)"]
style D fill:#ef6c00,color:#fff
style C fill:#ef6c00,color:#fff
Fifteen calls to compute fib(5) = 5. fib(3) is computed twice (highlighted), fib(2) three times, fib(1) five times. The number of calls is itself a Fibonacci-like recurrence: , , , (all computed by script). It grows as with , so fib(50) would take about calls: minutes in C++, hours in Python. The depth is only ; the width is exponential.
Rung 2: memoisation, time, space
Store each fib(k) the first time it is computed and return the stored value afterwards. There are only distinct subproblems, each computed once with work, so total. The recursion tree collapses to a path: each orange node becomes a cache hit. This is top-down dynamic programming, and the general recipe is: write the recursion, notice that the arguments range over a small set, cache on the arguments. Module 6 is twenty lessons on choosing the arguments.
Rung 3: iteration, time, space
Compute fib(0), fib(1), ..., fib(n) in order, keeping only the last two. Same subproblems as rung 2, evaluated in dependency order so that no cache is needed and no stack is used. Bottom-up dynamic programming. The loop invariant: at the start of iteration , (a, b) == (fib(k), fib(k+1)).
Rung 4: fast doubling,
The identities and let you compute from in arithmetic operations. It is fast exponentiation again, with the progress measure . Equivalent to raising the matrix to the -th power, which Module 6's matrix-exponentiation lesson generalises to every linear recurrence.
| Rung | Technique | Time | Space | Why it improves |
|---|---|---|---|---|
| 1 | Naive recursion | stack | — | |
| 2 | Memoised recursion | cache + stack | Each of the subproblems is solved once instead of exponentially often. | |
| 3 | Bottom-up loop | Dependency order removes the cache and the stack. | ||
| 4 | Fast doubling | or | Halving instead of decrementing it. |
The solution to practice problem 2 below contains rungs 1 to 3 with a cross-check.
Converting recursion to iteration
Three techniques, in increasing order of generality.
1. Accumulators and tail recursion
If the recursion is head-recursive only because it combines the result after the call (n * factorial(n-1), 1 + length(rest)), move the pending work into an extra parameter so the call becomes a tail call (factorial_acc(n-1, acc*n)). A tail-recursive function is a loop in disguise: replace the call with assignments to the parameters and a jump to the top. factorial_acc becomes while n > 0: acc *= n; n -= 1.
This is what a compiler doing tail-call elimination would do for you. Whether yours does:
- C++: compilers may. GCC and Clang perform sibling-call optimisation at
-O2(-foptimize-sibling-calls), and MSVC does similar in release builds, but no standard guarantees it, and it is easily defeated (destructors running after the call, taking the address of a local). Do not rely on it for correctness. - Java: the JVM does not eliminate tail calls. Stack frames are observable (security checks historically walked the stack; stack traces must be accurate), and the bytecode has no tail-call instruction. Scala and Kotlin implement
@tailrec/tailrecby rewriting self-calls into loops at compile time, which is the only way to get it on the JVM. - Python: CPython deliberately does not. Guido van Rossum's 2009 posts explain the reasoning: tail-call elimination destroys stack traces, which the language values more than deep recursion, and it is "unpythonic" to encourage recursion where a loop is clearer.
- JavaScript: ES2015 specified proper tail calls, but only JavaScriptCore (Safari) shipped them; V8 (Node, Chrome) implemented and then removed them in 2017 over debugging and performance concerns, and SpiderMonkey never shipped. In practice: no.
So in three of the four course languages, tail recursion saves you nothing at run time, and you must do the rewrite yourself.
2. Explicit stack
Any recursion can be made iterative by managing the stack yourself: push what the recursive call would have received, pop and process in a loop. For traversals, where the "pending work" is just "visit these children", the explicit stack is a list of nodes (plus any per-frame state, like depth). The depth_iter and flatten_iter functions in the implementation section do exactly this: depth_iter pushes (node, depth) pairs; flatten_iter pushes items in reverse so that the leftmost pops first and output order is preserved.
For head-recursive functions with real post-processing (in-order traversal, evaluating an expression tree), the explicit stack needs to record where you are in each frame, typically as a (node, state) pair or by pushing a marker. Module 3's traversals lesson does the in-order case in full; Module 4's DFS lesson does the general technique for graphs, where getting pre-order and post-order right iteratively is the whole trick behind iterative topological sort and SCC algorithms.
3. Rewriting the algorithm
Sometimes the iterative algorithm is simply different and better: fast exponentiation by scanning bits (the power_iter function) is not a mechanical transform of the recursive version, it is a different association of the same product. Bottom-up DP (rung 3 above) is not a transform of memoised recursion, it is the same subproblems in dependency order. When the recursion's structure is a DAG of subproblems rather than a tree, evaluating them in topological order replaces both the recursion and the cache.
When to convert
Convert when depth can exceed the stack (lists, path-like graphs, in Python), when per-call overhead matters in a hot loop (recursion in Python costs roughly a microsecond per call), or when you need to pause and resume the traversal (an iterator over a tree must hold its position in an explicit stack because it cannot stay inside a recursive call between next() calls). Otherwise leave it recursive: the recursive version is the one you can prove.
Mutual recursion
Two or more functions that call each other. The progress measure must decrease across the cycle of calls, not necessarily on each individual call.
The textbook example is parity: is_even(n) = True if n == 0 else is_odd(n-1) and is_odd(n) = False if n == 0 else is_even(n-1). The real one is a recursive descent parser. An arithmetic grammar
expr := term (('+' | '-') term)*
term := factor (('*' | '/') factor)*
factor := NUMBER | '(' expr ')'
becomes three functions, parse_expr calls parse_term calls parse_factor, and parse_factor calls parse_expr for a parenthesised sub-expression. The progress measure is the number of unconsumed tokens: parse_factor consumes the ( before calling parse_expr, so the cycle always makes progress. Recursion depth equals the nesting depth of parentheses, which is why hand-written parsers for JSON and other formats impose a maximum nesting depth (see real-world uses). Module 7's regex-engines lesson and the DP module's expression problems both use this skeleton.
Common recursive patterns
Five shapes cover most recursive code you will write in this course.
Linear recursion on or on the tail of a list: factorial, list length, reverse. Depth ; usually better as a loop.
Divide and conquer: split into parts, recurse on each, combine. Merge sort, quicksort, fast exponentiation, closest pair, Karatsuba. Depth when the split is balanced; cost from the Master theorem. Module 5.
Tree recursion returning a tuple. When a tree computation needs two facts about each subtree, return both from one traversal instead of making two. The classic: "is this tree height-balanced?" needs the height and the balanced-ness of each subtree, so return (is_balanced, height) and combine: balanced iff both children balanced and heights differ by at most 1. One pass, , instead of the or you get from calling a separate height() inside is_balanced(). Module 3's tree-patterns lesson is built on this idea.
Backtracking skeleton. Build a partial solution, and at each step try every legal extension, recurse, then undo the extension:
# fragment — backtracking skeleton
def backtrack(partial, choices):
if is_complete(partial):
record(partial)
return
for c in choices:
if is_legal(partial, c):
partial.append(c) # choose
backtrack(partial, choices) # explore
partial.pop() # unchoose
The progress measure is the number of positions left to fill. The pop() is the step people forget; without it the partial solution leaks state into sibling branches. Problems 7 and 8 below (Generate Parentheses, Permutations) are this skeleton with different is_legal. Module 5's backtracking lesson adds pruning and bitmask state.
Memoised recursion. Any recursion whose arguments range over a small set, with a cache keyed on the arguments. Fibonacci above; most of Module 6.
Complexity of recursive code
Time: write the recurrence and solve it with the complexity lesson's tools. Linear recursion on with work is . Halving recursion with work is . Two calls on halves with linear combine is . Two calls on and is exponential. Backtracking is bounded by the number of partial solutions explored: for permutations, for subsets, Catalan numbers for balanced parentheses, before pruning.
Space: for the stack plus whatever you allocate. Fast exponentiation is stack recursive, iterative. Tree recursion is , the height, which is for balanced trees and for degenerate ones. Backtracking is plus the output.
Constants: a function call costs more than a loop iteration in every language: tens of nanoseconds in C++ and Java (frame setup, possibly defeating inlining), about a microsecond in CPython. For small- hot paths, the iterative version wins on constants even when the complexity is identical; for the recursion in a divide-and-conquer sort, library implementations cut over to insertion sort for small subarrays precisely to avoid the call overhead near the leaves.
Implementation
Three functions, each in a recursive and an explicit-stack iterative version, with the same tests in all four languages: fast exponentiation (the trace-table example), the depth of a binary tree (structural recursion on a tree), and flattening a nested list (structural recursion on a list-of-lists). The TypeScript version uses bigint so that is exact.
from __future__ import annotations
from dataclasses import dataclass
# ---------- 1. power(x, n): recursive vs iterative fast exponentiation ----------
def power_rec(x: int, n: int) -> int:
"""x^n in O(log n) multiplications. Progress measure: n halves every call."""
if n == 0:
return 1
half = power_rec(x, n // 2)
return half * half * x if n % 2 else half * half
def power_iter(x: int, n: int) -> int:
"""Same idea without a stack: scan the bits of n from least significant."""
result = 1
while n > 0:
if n & 1:
result *= x
x *= x
n >>= 1
return result
# ---------- 2. tree depth: recursive vs explicit stack ----------
@dataclass
class Node:
val: int
left: Node | None = None
right: Node | None = None
def depth_rec(root: Node | None) -> int:
if root is None:
return 0
return 1 + max(depth_rec(root.left), depth_rec(root.right))
def depth_iter(root: Node | None) -> int:
"""Explicit stack of (node, depth) pairs replaces the call stack."""
if root is None:
return 0
best = 0
stack = [(root, 1)]
while stack:
node, d = stack.pop()
best = max(best, d)
if node.left:
stack.append((node.left, d + 1))
if node.right:
stack.append((node.right, d + 1))
return best
# ---------- 3. flatten a nested list: recursive vs explicit stack ----------
def flatten_rec(xs: list) -> list[int]:
out: list[int] = []
for item in xs:
if isinstance(item, list):
out.extend(flatten_rec(item)) # structural recursion on the sublist
else:
out.append(item)
return out
def flatten_iter(xs: list) -> list[int]:
"""Push items in reverse so the leftmost is popped first; order is preserved."""
out: list[int] = []
stack = list(reversed(xs))
while stack:
item = stack.pop()
if isinstance(item, list):
stack.extend(reversed(item))
else:
out.append(item)
return out
def main() -> None:
for x, n, want in [(3, 13, 1594323), (2, 10, 1024), (7, 0, 1), (5, 1, 5), (-2, 3, -8), (2, 62, 2 ** 62)]:
assert power_rec(x, n) == want, (x, n)
assert power_iter(x, n) == want, (x, n)
# 1
# / \
# 2 3
# / \
# 4 5
# /
# 6
tree = Node(1, Node(2, Node(4, Node(6))), Node(3, None, Node(5)))
assert depth_rec(tree) == 4
assert depth_iter(tree) == 4
assert depth_rec(None) == 0 and depth_iter(None) == 0
assert depth_rec(Node(9)) == 1 and depth_iter(Node(9)) == 1
nested = [1, [2, [3, 4], 5], [], [[6]], 7]
assert flatten_rec(nested) == [1, 2, 3, 4, 5, 6, 7]
assert flatten_iter(nested) == [1, 2, 3, 4, 5, 6, 7]
assert flatten_rec([]) == [] and flatten_iter([[[]]]) == []
print("all tests passed")
if __name__ == "__main__":
main()
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
public class RecursionVsIteration {
// ---------- 1. power(x, n): recursive vs iterative fast exponentiation ----------
static long powerRec(long x, int n) {
if (n == 0) return 1; // base case
long half = powerRec(x, n / 2); // progress: n halves
return (n % 2 == 1) ? half * half * x : half * half;
}
static long powerIter(long x, int n) {
long result = 1;
while (n > 0) {
if ((n & 1) == 1) result *= x;
x *= x;
n >>= 1;
}
return result;
}
// ---------- 2. tree depth: recursive vs explicit stack ----------
static final class Node {
int val; Node left, right;
Node(int val, Node left, Node right) { this.val = val; this.left = left; this.right = right; }
Node(int val) { this(val, null, null); }
}
static int depthRec(Node root) {
if (root == null) return 0;
return 1 + Math.max(depthRec(root.left), depthRec(root.right));
}
static int depthIter(Node root) {
if (root == null) return 0;
int best = 0;
Deque<Node> nodes = new ArrayDeque<>();
Deque<Integer> depths = new ArrayDeque<>();
nodes.push(root); depths.push(1);
while (!nodes.isEmpty()) {
Node node = nodes.pop(); int d = depths.pop();
best = Math.max(best, d);
if (node.left != null) { nodes.push(node.left); depths.push(d + 1); }
if (node.right != null) { nodes.push(node.right); depths.push(d + 1); }
}
return best;
}
// ---------- 3. flatten a nested list: recursive vs explicit stack ----------
// Items are either Integer or List<Object>.
static List<Integer> flattenRec(List<Object> xs) {
List<Integer> out = new ArrayList<>();
for (Object item : xs) {
if (item instanceof List<?> sub) {
@SuppressWarnings("unchecked") List<Object> s = (List<Object>) sub;
out.addAll(flattenRec(s));
} else {
out.add((Integer) item);
}
}
return out;
}
static List<Integer> flattenIter(List<Object> xs) {
List<Integer> out = new ArrayList<>();
Deque<Object> stack = new ArrayDeque<>();
for (int i = xs.size() - 1; i >= 0; i--) stack.push(xs.get(i)); // reverse so leftmost pops first
while (!stack.isEmpty()) {
Object item = stack.pop();
if (item instanceof List<?> sub) {
for (int i = sub.size() - 1; i >= 0; i--) stack.push(sub.get(i));
} else {
out.add((Integer) item);
}
}
return out;
}
static List<Object> L(Object... items) { return new ArrayList<>(Arrays.asList(items)); }
public static void main(String[] args) {
long[][] cases = {{3, 13, 1594323L}, {2, 10, 1024}, {7, 0, 1}, {5, 1, 5}, {-2, 3, -8}, {2, 62, 1L << 62}};
for (long[] c : cases) {
if (powerRec(c[0], (int) c[1]) != c[2]) throw new AssertionError("powerRec " + Arrays.toString(c));
if (powerIter(c[0], (int) c[1]) != c[2]) throw new AssertionError("powerIter " + Arrays.toString(c));
}
Node tree = new Node(1, new Node(2, new Node(4, new Node(6), null), null), new Node(3, null, new Node(5)));
if (depthRec(tree) != 4 || depthIter(tree) != 4) throw new AssertionError("depth");
if (depthRec(null) != 0 || depthIter(null) != 0) throw new AssertionError("empty");
if (depthRec(new Node(9)) != 1 || depthIter(new Node(9)) != 1) throw new AssertionError("leaf");
List<Object> nested = L(1, L(2, L(3, 4), 5), L(), L(L(6)), 7);
List<Integer> want = List.of(1, 2, 3, 4, 5, 6, 7);
if (!flattenRec(nested).equals(want)) throw new AssertionError("flattenRec " + flattenRec(nested));
if (!flattenIter(nested).equals(want)) throw new AssertionError("flattenIter " + flattenIter(nested));
if (!flattenRec(L()).isEmpty() || !flattenIter(L(L(L()))).isEmpty()) throw new AssertionError("empty nested");
System.out.println("all tests passed");
}
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <memory>
#include <stack>
#include <utility>
#include <variant>
#include <vector>
// ---------- 1. power(x, n): recursive vs iterative fast exponentiation ----------
long long power_rec(long long x, int n) {
if (n == 0) return 1; // base case
long long half = power_rec(x, n / 2); // progress: n halves
return (n % 2 == 1) ? half * half * x : half * half;
}
long long power_iter(long long x, int n) {
long long result = 1;
while (n > 0) {
if (n & 1) result *= x;
x *= x;
n >>= 1;
}
return result;
}
// ---------- 2. tree depth: recursive vs explicit stack ----------
struct Node {
int val;
std::unique_ptr<Node> left, right;
explicit Node(int v) : val(v) {}
};
int depth_rec(const Node* root) {
if (!root) return 0;
return 1 + std::max(depth_rec(root->left.get()), depth_rec(root->right.get()));
}
int depth_iter(const Node* root) {
if (!root) return 0;
int best = 0;
std::stack<std::pair<const Node*, int>> st;
st.push({root, 1});
while (!st.empty()) {
auto [node, d] = st.top(); st.pop();
best = std::max(best, d);
if (node->left) st.push({node->left.get(), d + 1});
if (node->right) st.push({node->right.get(), d + 1});
}
return best;
}
// ---------- 3. flatten a nested list: recursive vs explicit stack ----------
struct Nested;
using Item = std::variant<int, std::vector<Nested>>;
struct Nested { Item item; };
std::vector<Nested> L(std::initializer_list<Nested> xs) { return std::vector<Nested>(xs); }
Nested I(int v) { return Nested{v}; }
Nested S(std::vector<Nested> v) { return Nested{std::move(v)}; }
void flatten_rec_into(const std::vector<Nested>& xs, std::vector<int>& out) {
for (const Nested& n : xs) {
if (const int* v = std::get_if<int>(&n.item)) out.push_back(*v);
else flatten_rec_into(std::get<std::vector<Nested>>(n.item), out);
}
}
std::vector<int> flatten_rec(const std::vector<Nested>& xs) {
std::vector<int> out; flatten_rec_into(xs, out); return out;
}
std::vector<int> flatten_iter(const std::vector<Nested>& xs) {
std::vector<int> out;
std::stack<const Nested*> st;
for (auto it = xs.rbegin(); it != xs.rend(); ++it) st.push(&*it); // reverse so leftmost pops first
while (!st.empty()) {
const Nested* n = st.top(); st.pop();
if (const int* v = std::get_if<int>(&n->item)) out.push_back(*v);
else {
const auto& sub = std::get<std::vector<Nested>>(n->item);
for (auto it = sub.rbegin(); it != sub.rend(); ++it) st.push(&*it);
}
}
return out;
}
int main() {
struct Case { long long x; int n; long long want; };
for (Case c : {Case{3, 13, 1594323}, Case{2, 10, 1024}, Case{7, 0, 1}, Case{5, 1, 5}, Case{-2, 3, -8}, Case{2, 62, 1LL << 62}}) {
assert(power_rec(c.x, c.n) == c.want);
assert(power_iter(c.x, c.n) == c.want);
}
auto tree = std::make_unique<Node>(1);
tree->left = std::make_unique<Node>(2);
tree->left->left = std::make_unique<Node>(4);
tree->left->left->left = std::make_unique<Node>(6);
tree->right = std::make_unique<Node>(3);
tree->right->right = std::make_unique<Node>(5);
assert(depth_rec(tree.get()) == 4 && depth_iter(tree.get()) == 4);
assert(depth_rec(nullptr) == 0 && depth_iter(nullptr) == 0);
Node leaf(9);
assert(depth_rec(&leaf) == 1 && depth_iter(&leaf) == 1);
std::vector<Nested> nested = L({I(1), S(L({I(2), S(L({I(3), I(4)})), I(5)})), S(L({})), S(L({S(L({I(6)}))})), I(7)});
std::vector<int> want = {1, 2, 3, 4, 5, 6, 7};
assert(flatten_rec(nested) == want);
assert(flatten_iter(nested) == want);
assert(flatten_rec(L({})).empty() && flatten_iter(L({S(L({S(L({}))}))})).empty());
std::cout << "all tests passed\n";
return 0;
}
import assert from "node:assert/strict";
// ---------- 1. power(x, n): recursive vs iterative fast exponentiation ----------
// BigInt so 2^62 is exact (Number loses precision above 2^53).
function powerRec(x: bigint, n: number): bigint {
if (n === 0) return 1n; // base case
const half = powerRec(x, Math.floor(n / 2)); // progress: n halves
return n % 2 === 1 ? half * half * x : half * half;
}
function powerIter(x: bigint, n: number): bigint {
let result = 1n;
while (n > 0) {
if (n & 1) result *= x;
x *= x;
n >>= 1;
}
return result;
}
// ---------- 2. tree depth: recursive vs explicit stack ----------
type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };
const node = (val: number, left: TreeNode | null = null, right: TreeNode | null = null): TreeNode => ({ val, left, right });
function depthRec(root: TreeNode | null): number {
if (root === null) return 0;
return 1 + Math.max(depthRec(root.left), depthRec(root.right));
}
function depthIter(root: TreeNode | null): number {
if (root === null) return 0;
let best = 0;
const stack: Array<[TreeNode, number]> = [[root, 1]];
while (stack.length > 0) {
const [cur, d] = stack.pop()!;
best = Math.max(best, d);
if (cur.left) stack.push([cur.left, d + 1]);
if (cur.right) stack.push([cur.right, d + 1]);
}
return best;
}
// ---------- 3. flatten a nested list: recursive vs explicit stack ----------
type Nested = number | Nested[];
function flattenRec(xs: Nested[]): number[] {
const out: number[] = [];
for (const item of xs) {
if (Array.isArray(item)) out.push(...flattenRec(item));
else out.push(item);
}
return out;
}
function flattenIter(xs: Nested[]): number[] {
const out: number[] = [];
const stack: Nested[] = [...xs].reverse(); // reverse so leftmost pops first
while (stack.length > 0) {
const item = stack.pop()!;
if (Array.isArray(item)) {
for (let i = item.length - 1; i >= 0; i--) stack.push(item[i]);
} else {
out.push(item);
}
}
return out;
}
function main(): void {
const cases: Array<[bigint, number, bigint]> = [[3n, 13, 1594323n], [2n, 10, 1024n], [7n, 0, 1n], [5n, 1, 5n], [-2n, 3, -8n], [2n, 62, 2n ** 62n]];
for (const [x, n, want] of cases) {
assert.equal(powerRec(x, n), want);
assert.equal(powerIter(x, n), want);
}
const tree = node(1, node(2, node(4, node(6))), node(3, null, node(5)));
assert.equal(depthRec(tree), 4);
assert.equal(depthIter(tree), 4);
assert.equal(depthRec(null), 0);
assert.equal(depthIter(null), 0);
assert.equal(depthRec(node(9)), 1);
assert.equal(depthIter(node(9)), 1);
const nested: Nested[] = [1, [2, [3, 4], 5], [], [[6]], 7];
assert.deepEqual(flattenRec(nested), [1, 2, 3, 4, 5, 6, 7]);
assert.deepEqual(flattenIter(nested), [1, 2, 3, 4, 5, 6, 7]);
assert.deepEqual(flattenRec([]), []);
assert.deepEqual(flattenIter([[[]]]), []);
console.log("all tests passed");
}
main();
Points worth noticing in the code. power_rec matches the first trace table exactly, including the association half * half * x. flatten_iter must push children in reverse so that the leftmost is on top of the stack; forgetting this produces a correctly flattened but reversed list, which is the standard bug in iterative pre-order traversals. The Java and C++ nested-list versions are heavier because the type "integer or list of these" needs a tagged representation (Object with instanceof, std::variant); Python and TypeScript get it for free from dynamic typing.
Real-world uses
- Parsers and compilers. Nearly every hand-written parser (Clang's C++ front end, V8's JavaScript parser, most JSON and YAML libraries, Go's
go/parser) is a recursive-descent parser: one mutually recursive function per grammar rule. Because depth equals nesting depth, they cap it: Jackson (Java's dominant JSON library) limits nesting to 1000 by default since version 2.15; Python'sjsonmodule raisesRecursionErroron deeply nested input; V8's parser has an explicit stack-overflow check. Deeply nested input is a known denial-of-service vector precisely because of the recursion. - Operating-system kernels avoid recursion. The Linux kernel runs each thread's kernel code on a fixed stack, 16 KB on x86-64, so kernel code is written iteratively and recursion is reviewed as a bug. The same is true of most embedded and real-time systems. OS Algorithms and Virtual Memory show the iterative page-table and scheduler walks that result.
- Garbage collectors. Marking live objects is a graph traversal, naturally recursive, but a collector cannot risk overflowing its own stack on a long linked list. Every production tracing collector (HotSpot, V8's Orinoco, Go's) uses an explicit mark stack with overflow handling, the explicit-stack conversion from this lesson in its most consequential form.
- File systems and build tools. Directory traversal (
find,rsync, Git's tree walk,webpack's module graph) is structural recursion over a tree. Git stores a commit's tree as recursive tree objects, andgitwalks them recursively with a depth that equals the directory depth, which is small enough not to matter. - Sorting libraries.
std::sort(introsort) and Java's dual-pivot quicksort recurse on the smaller partition and loop on the larger, which bounds the stack at regardless of pivot quality, a direct application of "convert the tail call to a loop". Timsort is iterative throughout. - Databases and B-trees. B-tree descent is recursion of depth , typically 3 or 4 levels for a billion keys, and is written iteratively in most engines. Indexing Deep Dive and Storage Engines show it; LSM-tree compaction is a merge (Proof 3) over sorted runs.
- Interview and contest code. DFS, tree problems, backtracking and top-down DP are all recursive by default, and the stack-limit table above is why Python contestants write
sys.setrecursionlimit(1 << 25)and run DFS in a thread with a large stack, or convert to iteration.
Pitfalls & edge cases
Missing or unreachable base case. fib(n) = fib(n-1) + fib(n-2) with only if n == 0: return 0 recurses forever from fib(1) into negative numbers. Every path to a recursive call must be shown to reach a base case; check negative and zero inputs explicitly. For binary search, lo > hi (empty range) is the base case, and both lo <= hi and lo < hi loop conditions have their own off-by-one traps on the matching return.
No progress. bsearch(a, mid, hi, t) instead of mid + 1 loops forever when lo == hi. power(x, n - 2) for odd never reaches 0 from an odd start if the base case is only n == 0. The fix is always the same: name the progress measure and verify it strictly decreases in every recursive call.
Shared mutable state across branches. In backtracking, forgetting to undo (partial.pop(), used[i] = False) corrupts sibling branches. Passing a mutable list by reference and appending in one branch leaks into the next. Either undo on return, or pass a fresh copy (correct but per call). Python's mutable default argument (def f(x, acc=[])) is the same bug in disguise: the default list is shared across all calls.
Exponential blowup from repeated subproblems. Naive Fibonacci, naive "number of paths in a grid", naive edit distance. The signature is a recursion with two or more calls whose arguments overlap. Draw the tree; if subtrees repeat, memoise. A function of integer arguments each ranging over values has at most distinct calls, so memoisation turns exponential into polynomial.
Deep recursion on linked lists and path graphs. Recursing on node.next has depth equal to list length; Python dies at 1000 nodes, Java at a few thousand to tens of thousands depending on frame size. Any recursion whose depth is rather than needs the explicit-stack rewrite or a loop for inputs beyond the toy range. This includes recursive DFS on sparse graphs, which is why contest DFS in Python is iterative.
Off-by-one in range bounds. Inclusive versus exclusive hi; range(lo, hi) versus range(lo, hi + 1); mid versus mid + 1. Write the invariant in a comment ("a[lo..hi] inclusive may contain the target") and make every line respect it. Half of all binary-search bugs are a mismatch between the comment and the code.
Integer overflow in the combine step. half * half * x overflows 64-bit integers for beyond about ; in modular problems reduce after every multiplication (half * half % m * x % m), and in Java and C++ make sure half * half is computed in 64 bits (long/long long), since two 32-bit ints multiply to a 32-bit result. Python's integers are arbitrary precision, which hides this bug until you port the code.
Trusting tail recursion. In Python, Java and JavaScript a tail-recursive function uses exactly as much stack as a head-recursive one. Writing in accumulator style is a useful step toward a loop, but it is not the loop.
Stack size and recursion limit are different things in Python. sys.setrecursionlimit(10**6) lifts the interpreter's counter; before Python 3.12 the C stack could still overflow and crash the process (a segmentation fault rather than a RecursionError) at a depth that depended on the platform. Running the recursive code in a threading.Thread after threading.stack_size(512 * 1024 * 1024) was, and for C-level recursion still is, the way to get a bigger C stack.
Variations
- Memoisation and dynamic programming. Recursion plus a cache (top-down) or recursion evaluated in dependency order (bottom-up). Module 6 in its entirety.
- Iterative deepening. For search problems with unknown depth (game trees, IDA*), run a depth-limited recursion with limits ; total work is dominated by the last iteration when the branching factor is more than 1. Module 4's DFS lesson.
- Continuation-passing style and trampolines. Pass "what to do with the result" as a function argument so that every call is a tail call, then run the tail calls from a loop (a trampoline) instead of the stack. This is how deep recursion is made safe in languages without tail-call elimination when an explicit stack would be awkward. Rare in interviews, common in interpreters and functional-language runtimes.
- Generators and coroutines. A recursive generator (
yield fromin Python,yield*in JavaScript) is recursion that can be paused: in-order traversal as an iterator, flattening a nested structure lazily. The runtime keeps each generator's frame on the heap, so the stack-depth limit still applies to the chain ofyield fromdelegations. - Recursion schemes (folds).
reduce/foldis structural recursion over a list abstracted into a higher-order function; a fold over a tree ("catamorphism") is the same for trees. Recognising that a tree function is a fold tells you it is and lets you write it as one pass. - Well-founded induction and termination proofs. When the progress measure is not a single integer (lexicographic pairs, multisets, ordinals), the same argument works over any well-founded order. The Ackermann function terminates by induction on the pair ordered lexicographically; mutual recursion often needs a measure on the pair (function, argument).
- Divide and conquer, backtracking, DFS. The three biggest recursion-shaped families each have a module of their own (5, 5 and 4 respectively).
Practice ladder
Ten problems, easy to hard. Each teaches one thing from this lesson. Solutions are in Python and run as part of this page's tests.
1. Fibonacci Number (LeetCode 509) · Easy. Compute the -th Fibonacci number. Teaches the full ladder: write the naive recursion, watch it blow up around , memoise, then iterate.
Hint
Three versions, in this order: naive recursion, @lru_cache on the same function, then a loop keeping two variables. Confirm all three agree for .
Solution
from functools import lru_cache
def fib_naive(n: int) -> int:
return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)
@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
def fib_iter(n: int) -> int:
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
for n in range(20):
assert fib_naive(n) == fib_memo(n) == fib_iter(n)
assert fib_iter(90) == 2880067194370816120
print("ok")
Naive ; memoised time and space; iterative time, space. The loop invariant for fib_iter: at the start of iteration , (a, b) == (F_k, F_{k+1}).
2. Pow(x, n) (LeetCode 50) · Medium. Compute for a real and a 32-bit integer that may be negative. Teaches fast exponentiation with the negative-exponent edge case and the overflow trap in languages with fixed-width integers.
Hint
Handle by inverting and negating . Then halve each step. In Java/C++, negate into a long first: -Integer.MIN_VALUE overflows.
Solution
def my_pow(x: float, n: int) -> float:
"""LeetCode 50. Handle negative n by inverting; O(log n)."""
if n < 0:
x, n = 1 / x, -n
result = 1.0
while n:
if n & 1:
result *= x
x *= x
n >>= 1
return result
assert abs(my_pow(2.0, 10) - 1024.0) < 1e-9
assert abs(my_pow(2.1, 3) - 9.261) < 1e-9
assert abs(my_pow(2.0, -2) - 0.25) < 1e-12
assert my_pow(1.0, 2**31 - 1) == 1.0
print("ok")
time, space. The recursive version is the trace-table algorithm; the iterative one above is the second trace table.
3. Merge Two Sorted Lists (LeetCode 21) · Easy. Merge two sorted linked lists into one sorted list. Do it recursively first: it is Proof 3 as code. Then do it iteratively with a dummy head and note the depth difference.
Hint
The smaller head is the answer's head; its next is the merge of the rest. Which call has the smaller total length?
4. Reverse Linked List (LeetCode 206) · Easy. Reverse a singly linked list. The recursive version is the cleanest illustration of head recursion with post-processing: reverse the tail, then make the old successor point back. Then observe that it is stack and write the three-pointer loop.
Hint
reverse(head): if the list has 0 or 1 nodes, return it. Otherwise new_head = reverse(head.next); then head.next.next = head; head.next = None.
Solution
class ListNode:
def __init__(self, val: int, next: "ListNode | None" = None):
self.val, self.next = val, next
def from_list(xs: list[int]) -> "ListNode | None":
head = None
for v in reversed(xs):
head = ListNode(v, head)
return head
def to_list(node: "ListNode | None") -> list[int]:
out = []
while node:
out.append(node.val); node = node.next
return out
def merge_rec(a: "ListNode | None", b: "ListNode | None") -> "ListNode | None":
"""Head recursion: the smaller head is followed by the merge of the rest."""
if a is None: return b
if b is None: return a
if a.val <= b.val:
a.next = merge_rec(a.next, b); return a
b.next = merge_rec(a, b.next); return b
def reverse_rec(head: "ListNode | None") -> "ListNode | None":
if head is None or head.next is None:
return head
new_head = reverse_rec(head.next) # reverse the tail first
head.next.next = head # old successor now points back at us
head.next = None
return new_head
assert to_list(merge_rec(from_list([1, 2, 4]), from_list([1, 3, 4]))) == [1, 1, 2, 3, 4, 4]
assert to_list(merge_rec(None, from_list([0]))) == [0]
assert to_list(reverse_rec(from_list([1, 2, 3, 4, 5]))) == [5, 4, 3, 2, 1]
assert to_list(reverse_rec(None)) == []
print("ok")
Both time and stack. This covers problems 3 and 4. In Python, both crash past 1000 nodes; the iterative versions in Linked Lists are what you would ship.
5. Gray Code (LeetCode 89) · Medium. Produce a sequence of all -bit values where consecutive values differ in one bit. Teaches a recursive construction with a non-obvious inductive proof: the -bit code is the -bit code followed by its reverse with the top bit set.
Hint
Prove by induction that reflecting the -bit code and prefixing a 1 keeps the one-bit-difference property at the seam. The closed form i ^ (i >> 1) is a second, iterative answer; for 3 bits it gives 0, 1, 3, 2, 6, 7, 5, 4.
6. Decode String (LeetCode 394) · Medium. Expand a string like 3[a2[c]] to accaccacc. Teaches recursive descent on a tiny grammar, and then the explicit-stack conversion: push (prefix, repeat) at [, pop at ].
Hint
Recursive: a function that parses until it meets ] or the end, calling itself when it meets [. Iterative: a stack of (string_so_far, repeat_count).
7. Generate Parentheses (LeetCode 22) · Medium. List all well-formed strings of pairs of parentheses. Teaches the backtracking skeleton with a legality check, and that the output size is the Catalan number (42 for ).
Hint
Keep counts of opens and closes used. You may add ( if opens ; you may add ) if closes opens. Undo after each recursive call.
Solution
def generate_parenthesis(n: int) -> list[str]:
"""Backtracking skeleton: choose '(' while opens remain, ')' while it keeps the prefix valid."""
out: list[str] = []
def go(prefix: list[str], opened: int, closed: int) -> None:
if len(prefix) == 2 * n:
out.append("".join(prefix)); return
if opened < n:
prefix.append("("); go(prefix, opened + 1, closed); prefix.pop()
if closed < opened:
prefix.append(")"); go(prefix, opened, closed + 1); prefix.pop()
go([], 0, 0)
return out
assert generate_parenthesis(1) == ["()"]
assert sorted(generate_parenthesis(3)) == sorted(["((()))", "(()())", "(())()", "()(())", "()()()"])
assert len(generate_parenthesis(5)) == 42 # Catalan number C_5
def permutations(nums: list[int]) -> list[list[int]]:
out: list[list[int]] = []
used = [False] * len(nums)
def go(path: list[int]) -> None:
if len(path) == len(nums):
out.append(path[:]); return
for i, x in enumerate(nums):
if not used[i]:
used[i] = True; path.append(x)
go(path)
path.pop(); used[i] = False
go([])
return out
assert len(permutations([1, 2, 3, 4])) == 24
assert sorted(permutations([1, 2, 3])) == [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
print("ok")
Generate Parentheses: output-sensitive, depth . Permutations (problem 8): , depth . Both are the skeleton with a different is_legal; note the pop() and used[i] = False undo steps.
8. Permutations (LeetCode 46) · Medium. All orderings of a list of distinct numbers. The backtracking skeleton with a used array; the solution is included under problem 7. Teaches undoing shared state, and that the recursion tree has leaves.
Hint
At each depth choose any unused element, mark it used, recurse, unmark it.
9. Tower of Hanoi (CSES 2165) · Medium. Move discs between pegs under the usual rules, printing the moves. Teaches a recursion whose proof is the algorithm: to move discs, move out of the way, move the bottom one, move back; and the recurrence , which is also provably optimal.
Hint
hanoi(n, src, dst, aux): if do nothing; else hanoi(n-1, src, aux, dst), move one disc src → dst, hanoi(n-1, aux, dst, src). Prove the move count by induction.
Solution
def hanoi(n: int, src: str, dst: str, aux: str, moves: list[tuple[str, str]]) -> None:
"""Move n discs src -> dst. 2^n - 1 moves, provably minimal."""
if n == 0:
return
hanoi(n - 1, src, aux, dst, moves)
moves.append((src, dst))
hanoi(n - 1, aux, dst, src, moves)
def simulate(n: int, moves: list[tuple[str, str]]) -> bool:
pegs = {"A": list(range(n, 0, -1)), "B": [], "C": []}
for s, d in moves:
if not pegs[s] or (pegs[d] and pegs[d][-1] < pegs[s][-1]):
return False
pegs[d].append(pegs[s].pop())
return pegs["C"] == list(range(n, 0, -1))
for n in range(0, 8):
moves: list[tuple[str, str]] = []
hanoi(n, "A", "C", "B", moves)
assert len(moves) == 2 ** n - 1 and simulate(n, moves)
def decode_string(s: str) -> str:
"""LeetCode 394 via an explicit stack: push (prefix, repeat) at '[' and pop at ']'."""
stack: list[tuple[str, int]] = []
cur, k = "", 0
for ch in s:
if ch.isdigit():
k = k * 10 + int(ch)
elif ch == "[":
stack.append((cur, k)); cur, k = "", 0
elif ch == "]":
prev, rep = stack.pop(); cur = prev + cur * rep
else:
cur += ch
return cur
assert decode_string("3[a]2[bc]") == "aaabcbc"
assert decode_string("3[a2[c]]") == "accaccacc"
assert decode_string("2[abc]3[cd]ef") == "abcabccdcdcdef"
print("ok")
Hanoi: moves, depth ; the simulator is a brute-force checker of the kind Testing & Debugging Algorithms recommends. The second function is problem 6 solved iteratively; its time is .
10. Flatten Nested List Iterator (LeetCode 341) · Medium. Provide next() and hasNext() over a nested list of integers, lazily. Teaches why recursion must become an explicit stack when the traversal has to pause between calls: an iterator cannot stay inside a recursive call. The flatten_iter function in the implementation section is the eager version; the iterator keeps the same stack across calls.
Hint
Keep a stack of (list, index) pairs. hasNext() advances the top until it points at an integer, popping exhausted lists and pushing nested ones. next() returns that integer and advances the index.
Common mistakes & interview follow-ups
Interview follow-ups you should expect after any recursive solution, with the short answers:
- "What is the recursion depth, and will it overflow?" Name it: for balanced divide and conquer (safe), for lists and degenerate trees (unsafe past about in Python, in Java/JS, in C++). Offer the explicit-stack rewrite.
- "Can you make it iterative?" Yes, always: accumulator-to-loop for tail calls, explicit stack otherwise. Say which applies and sketch it.
- "Why is the naive version slow?" Repeated subproblems; draw two overlapping subtrees of the recursion tree; propose memoisation and state the number of distinct subproblems.
- "Prove it is correct." Induction on the progress measure: state the base case, state the inductive hypothesis as "the recursive call returns the correct answer for the smaller input", show the combine step. Two to four sentences.
- "What is the space?" Stack depth plus explicit allocations; for memoised recursion, plus the cache.
- "What if the structure is a graph, not a tree?" Add a visited set; without it the recursion may not terminate. (The progress measure becomes "unvisited vertices remaining".)
- "What about tail-call optimisation?" Not available in Python, Java or JavaScript engines you will deploy on; possible but not guaranteed in C++. Do not rely on it.
The mistakes interviewers see most. Writing the recursive case before deciding the base case. Forgetting to return the recursive call's result (helper(n - 1) instead of return helper(n - 1)), which returns None/undefined from every non-base frame. Mutating a shared list in backtracking without undoing. Recursing on both halves when one would do (binary search written as a two-call tree). Assuming a tree is balanced when stating the depth. And saying "it is recursive so it is " without writing the recurrence.
Quick quiz
1. A function calls itself on and on and does other work, with memoisation on . Time and space?
Answer
time (each of distinct arguments computed once) and space (the cache plus a stack of depth ). Without memoisation, time.
2. Which of these is a valid progress measure for bsearch(a, lo, hi, t): (a) hi, (b) hi - lo + 1, (c) mid?
Answer
(b). hi alone does not decrease when recursing into the right half; mid is not a property of the call's arguments. The range size is non-negative and strictly decreases in both recursive calls.
3. In Python, does rewriting factorial(n) in accumulator (tail-recursive) form let you compute factorial(5000) with the default settings?
Answer
No. CPython performs no tail-call elimination, so the accumulator version still uses 5000 frames and exceeds the default limit of 1000. Use a loop (or math.prod(range(1, 5001))).
4. What is wrong with this backtracking code: path.append(x); go(path); with no pop()?
Answer
The chosen element is never removed, so every sibling branch after the first sees a longer path than it should; the function records wrong solutions or never reaches the completion check. Every "choose" needs a matching "unchoose".
5. State the loop invariant that proves the iterative power_iter(x, n) correct.
Answer
At the start of each iteration, with x0 and n0 the original arguments: result * x ** n == x0 ** n0. Initially result = 1, x = x0, n = n0. If the low bit of n is 1, result *= x and conceptually n -= 1, preserving the product; then x = x*x and n //= 2 (now even) preserve it since . At exit n = 0, so result == x0 ** n0.
Further reading
- CLRS, Introduction to Algorithms, 4th ed.: Section 2.1 (insertion sort and the loop-invariant template with exactly the initialization/maintenance/termination structure used here), Section 2.3 (merge sort and the correctness of merge), Chapter 4 (divide and conquer and the recurrences that result).
- Sedgewick & Wayne, Algorithms, 4th ed., Section 1.1 (recursion basics) and the discussion of recursion depth in Section 2.3 (quicksort recursing on the smaller side).
- Skiena, The Algorithm Design Manual, 3rd ed., Chapter 1.3 ("Reasoning about Correctness": induction and loop invariants) and Chapter 9 (combinatorial search and backtracking).
- Abelson & Sussman, Structure and Interpretation of Computer Programs, Section 1.2 ("Procedures and the Processes They Generate"): linear recursive vs iterative processes, tree recursion, and why Scheme guarantees tail-call elimination.
- Graham, Knuth & Patashnik, Concrete Mathematics, Chapter 1 (Tower of Hanoi as the opening example of recurrence and induction).
- Guido van Rossum, "Tail Recursion Elimination" and "Final Words on Tail Calls", Neopythonic blog, April 2009: why CPython does not do it.
- cp-algorithms: Binary Exponentiation (fast exponentiation and its applications), Fibonacci Numbers (fast doubling).
Where to go next
Previous: Complexity Analysis · Next: How Data Structures Live in Memory, which explains the constants that Big-O and recursion depth leave out.
Related: Recursion & Backtracking (the Module 5 overview), Trees (structural recursion in practice), Linked Lists (the iterative versions of problems 3 and 4), How to Solve Any Problem, Module 0 · Foundations.