Recursion

Solving a Problem in Terms of Itself

Recursion is a technique where a function calls itself on a smaller version of the same problem, until it reaches a case simple enough to solve directly. It is the programming counterpart of mathematical induction (Unit 1) and of recurrence relations — a problem defined in terms of smaller instances of itself.

Every recursive function needs two ingredients:

1. A base case — a smallest instance solved directly, without further recursion. This stops the recursion.
2. A recursive case — the function calls itself on a smaller subproblem and combines the result.

The classic example is the factorial: $n! = n \times (n-1)!$ with base case $0! = 1$. To compute $3!$, the function calls itself down to the base case and multiplies back up: $3! = 3 \times 2! = 3 \times 2 \times 1! = 3 \times 2 \times 1 = 6$. The recursion "unwinds" once the base case is hit.

The single most important rule: the recursive call must make progress toward the base case. If each call does not genuinely shrink the problem (reduce $n$, shorten the list, narrow the range), the recursion never terminates — the analogue of an infinite loop, causing a stack overflow as the pending calls pile up without resolving. A missing or unreachable base case is the defining recursion bug, exactly as omitting the base case invalidates an induction proof.

Recursion mirrors induction so closely that proving a recursive function correct is an induction: the base case establishes correctness for the smallest input, and the recursive case shows that if the function is correct on the smaller subproblem, it is correct on the larger one. Many problems — tree traversals, divide-and-conquer, and anything with self-similar structure — are far cleaner recursively than with loops.

Common pitfall: writing a recursion with no base case or one the calls never reach, so the function recurses forever (a stack overflow). Every recursive function needs a base case and each recursive call must move genuinely closer to it (a strictly smaller subproblem). This is exactly the induction requirement — a base case plus a step that reduces to a smaller instance; omitting either breaks both the program and the proof.

A stack of recursive call frames descending from 3! to 2! to 1! to the accent base case 0! = 1, then unwinding upward multiplying back to 6 — recursion with a base case.

$$n! = n \times (n-1)!,\quad 0! = 1$$