[Intermediate] — Two faces of one idea, and the single most important technique in this track for a programmer.
The idea
Recursion defines. Induction proves. They have the same shape because they are the same shape.
| Recursion | Induction | |
|---|---|---|
| Base | if (n == 0) return 1 | prove |
| Step | return n * fact(n-1) | prove |
| Gets you | a value for any | truth for all |
Write a recursive function and you’ve written the skeleton of an inductive proof. Which is why recursive code is easier to reason about than a loop even when it’s harder to write — the correctness argument comes with the structure.
Weak induction
To prove for all :
- Base case: prove
- Inductive step: assume (the inductive hypothesis), prove
Claim:
Base (): LHS , RHS . ✓
Step: assume it holds for . Then
which is the formula at .
Two things people get wrong:
Assuming is not circular. You’re proving the implication , and inside an implication you assume the antecedent. You are not assuming what you’re proving.
The base case is not a formality. Without it the chain has nothing to start from — and you can “prove” false statements. “All horses are the same colour” is the classic fallacious induction, and it fails precisely at the step from one horse to two.
Strong induction
Assume for all , not just .
Use it when the step needs to reach further back than one.
Claim: Every integer has a prime factorisation.
Step: let . If is prime, done. Otherwise with . By strong induction both and factorise — and note that and could be anywhere below , so weak induction’s single-step hypothesis wouldn’t reach them. Multiply the factorisations.
Weak and strong induction are logically equivalent — each proves the other. Strong is just more convenient, and it’s the natural fit for divide-and-conquer, where a problem of size becomes subproblems of size .
Structural induction
The version that matters most in computing. Induct over the structure of a recursively-defined object rather than over a number.
A binary tree is either empty, or a node with a left and right subtree. So:
- Base: prove
- Step: assume and , prove
Claim: a binary tree with nodes has null links.
Base: empty tree — 0 nodes, 1 null link. ✓
Step: a node with subtrees of and nodes has nodes, and by hypothesis null links, which is (nodes) + 1. ✓
This is the workhorse for anything tree-shaped, which is most of computing: ASTs, JSON, file systems, expression evaluation, semantic analysis, and type-soundness proofs.
It works because algebraic data types are recursively defined, and it’s why pattern matching on an enum feels like doing a proof: each arm is a case, and exhaustiveness checking is the compiler verifying you covered every constructor.
Recurrence relations
A sequence defined in terms of earlier terms.
That’s merge sort: split into two halves, recurse, merge in linear time. Solving the recurrence gives you the complexity.
The Master Theorem
For — the shape of every divide-and-conquer algorithm:
| Case | Condition | Result |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | , regular |
The intuition, which is more useful than the cases: compare the work at the leaves () against the work at the root (). Whichever dominates, wins; if they’re balanced, you pay a factor for the balance.
Worked examples worth recognising instantly:
| Recurrence | Solution | Algorithm |
|---|---|---|
| merge sort | ||
| tree traversal | ||
| binary search | ||
| worst-case quicksort | ||
| towers of Hanoi |
The two rows to compare are rows 1 and 2. Same recursion, different combine cost, and the whole difference between and comes from whether merging costs linear time. That’s the kind of thing you can’t see by staring at code and can see immediately from the recurrence. → Sorting
The Master Theorem doesn’t cover everything — unequal splits, non-polynomial . Then use the recursion tree method (draw the levels, sum the work per level) or substitution (guess, verify by induction). The recursion tree is the most intuitive and is usually enough.
Recursion in practice
Where the maths meets the machine.
Every recursive call costs a stack frame. Deep recursion overflows the stack — a hard limit around a few thousand frames in Python, more in C but still finite. → Processes and Threads
Tail calls can be optimised away. If the recursive call is the last operation, the frame can be reused, turning recursion into iteration. Guaranteed in Scheme and functional languages, not guaranteed in C/C++, and absent in Python and the JVM by design. Don’t rely on it unless your language promises it. → Optimisation
Naive recursion can be exponentially wasteful. Fibonacci recomputes the same subproblems:
Memoisation collapses it to by ensuring each subproblem is solved once. That observation is the whole of dynamic programming — overlapping subproblems plus optimal substructure. → Dynamic Programming
Any recursion can be made iterative with an explicit stack. Sometimes clearer, sometimes much worse. Use recursion when the data is recursive.
Well-founded recursion
Why does recursion terminate? Because each call is on something “smaller”, and you can’t descend forever.
Formally: the recursion must be on a well-founded partial order — one with no infinite descending chains. under is well-founded; is not, and under on is not (you can always halve).
The practical rule: identify what decreases and what its floor is. If you can’t name it, you may not have termination — the same variant argument as a loop, because it’s the same argument. → Proof Techniques
And this is why total-functional languages (Coq, Agda, Lean) reject recursion they can’t prove terminating. They must — a non-terminating function would let you “prove” anything, since an infinite loop inhabits every type. It’s the Curry–Howard correspondence enforcing itself.
Where induction shows up
Loop invariants — induction on iterations. → Proof Techniques
Algorithm correctness — every divide-and-conquer proof is strong induction.
Type soundness — “well-typed programs don’t go wrong” is proved by structural induction on typing derivations. → Type Systems
Compiler correctness — induction over the AST.
Protocol safety — “this invariant holds in every reachable state” is induction over execution steps. This is precisely what TLA+ checks, and what Raft’s safety proof does. → Raft
Recursive data structures — trees, lists, grammars, JSON. Define recursively, prove structurally.
Related
- Proof Techniques — the other methods
- Dynamic Programming — recursion plus memoisation
- Algorithms — where these complexities land
- Discrete maths map
Software engineering
Infrastructure & security
Computer science
Hardware & engineering