Recursion and Induction: Proving Code and Proving Math Are the Same Idea

A line of dominoes falls over completely as long as exactly two things are true: the first domino actually gets knocked over, and every domino that falls is close enough to knock over the next one. Given those two facts, you don't need to check each domino individually to know the whole line falls — the two facts together already guarantee it, for a line of any length.

That's mathematical induction, and it's a genuine proof technique, not just an analogy: to prove a statement is true for every whole number, prove it's true for the first number (the base case, "the first domino falls"), then prove that whenever it's true for some number, it's also true for the very next one (the inductive step, "each falling domino knocks over the next"). Those two proven facts, together, cover every number there is, the same way the two facts about the dominoes cover every domino in the line, no matter how long it is.

Recursion in code is the direct, practical mirror of this same idea: a recursive function solves a problem by handling the smallest, simplest version of it directly (the base case — the exact same role the first domino plays), and handling every larger version by doing a small piece of work and then trusting a smaller call to the same function to correctly handle the rest (the recursive step — the exact same role as one domino knocking over the next). A function that calculates factorial handles 1 directly as its base case, and for any larger number n, computes n times whatever the recursive call for n-1 returns — trusting that smaller call completely, the same way induction trusts that the previous domino falling guarantees the next one falls too.

This connection isn't just a cute parallel — it's the actual reason a working base case and a correctly shrinking recursive step are enough to trust a recursive function is correct for every input, without manually tracing through every possible input by hand. Proving a recursive function correct and proving a statement true by induction are, structurally, the identical argument applied to two different domains: one to a mathematical claim about all whole numbers, one to a piece of code that needs to work for every valid input it might receive.

The practical payoff of seeing this connection is knowing exactly what to check when a recursive function misbehaves: verify the base case actually stops the recursion correctly (the equivalent of confirming the first domino genuinely falls), and verify the recursive step is always making genuine progress toward that base case rather than looping in place (confirming each domino is actually close enough to knock over the next one) — those two checks, and nothing more exotic, are what a working recursive function actually depends on.