[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.

RecursionInduction
Baseif (n == 0) return 1prove
Stepreturn n * fact(n-1)prove
Gets youa 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 :

  1. Base case: prove
  2. 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:

CaseConditionResult
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:

RecurrenceSolutionAlgorithm
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.


↑ Back to Discrete Mathematics