Recursion

Recursion is induction's twin sibling. Induction proves a statement is true for every natural number by chaining base case and step; recursion defines a function at every natural number by combining a base value with a rule that builds on smaller cases. The factorial $n!$, the Fibonacci numbers, the Tower of Hanoi move-count, and every divide-and-conquer algorithm in your toolkit are recursive definitions in disguise. Once you see the pattern — say what happens at the base, then say how the answer at $n$ depends on smaller answers — you can build infinitely many objects from finite text, then prove their properties by induction.

Anatomy of a recursive definition

A function $f : \mathbb{N} \to S$ is defined recursively by giving:

• One or more base values: $f(0) = c_0,;f(1) = c_1,;\ldots$
• A recursive clause: a formula for $f(n)$ when $n$ is larger than the base cases, depending on $f(j)$ for some $j < n$.

The recursion is well-defined when every chain of recursive calls eventually reaches a base case. The most common way to guarantee that is to insist that the recursive clause only refers to smaller arguments. The clause $g(n) = g(n+1) - 1$ is not well-defined: computing $g(0)$ would require $g(1)$, then $g(2)$, forever.

Three canonical examples

Factorial. $0! = 1$ and $n! = n \cdot (n-1)!$ for $n \geq 1$. Unwinding gives $4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$.

Fibonacci. $F_0 = 0,;F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$. Two base values are needed because the rule reaches back two steps. The sequence starts $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots$

Tower of Hanoi. Let $T(n)$ be the smallest number of single-disk moves to transfer a stack of $n$ disks. Then $T(1) = 1$ and $T(n) = 2T(n-1) + 1$ for $n \geq 2$ — move the top $n-1$ disks to a spare peg (that's $T(n-1)$ moves), move the biggest disk (one move), then move the $n-1$ disks on top of it ($T(n-1)$ more). A short induction shows $T(n) = 2^n - 1$.

From recursion to closed form

A recursive definition tells you how to compute $f(n)$ step by step but rarely gives an explicit formula. Finding a closed form (when one exists) usually has two acts. Act 1: guess. Compute $f(0), f(1), f(2), \ldots$ and look for a pattern. Act 2: verify. Prove by induction that your conjectured formula matches. The Tower of Hanoi proof goes: compute $T(1) = 1,;T(2) = 3,;T(3) = 7,;T(4) = 15$. Conjecture $T(n) = 2^n - 1$. Verify base case $T(1) = 2^1 - 1 = 1$. Induction: $T(k+1) = 2T(k) + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 1$. $\blacksquare$

Pause and think: the definition $h(0) = 1,;h(n) = h(n - 2) + n$ for $n \geq 1$ looks innocent. Is it well-defined? Trace a computation of $h(1)$ and see what happens.

Try it

• Predict $F_7$ before computing. Then unwind: $F_2, F_3, F_4, F_5, F_6, F_7$ in order.
• Predict $5!$ first, then verify by recursion: $5! = 5 \cdot 4!$, then $4! = 4 \cdot 3!$, all the way down to the base case.
• Compute $T(5)$ for Tower of Hanoi using $T(n) = 2T(n-1) + 1$. Check against the closed form $2^5 - 1$.
• The sequence $a_1 = 1,;a_n = 2a_{n-1} + 1$ gives $1, 3, 7, 15, 31, \ldots$. Conjecture a closed form and verify your conjecture for $n = 6$.

A trap to watch for

A common pitfall is writing a "recursion" that points the wrong way — toward larger arguments. The definition $f(0) = 1,;f(n) = f(n+1) / 2$ is not a recursion at all; it cannot be evaluated. Another pitfall is forgetting that two base values are needed when the recursive clause reaches back two steps (as in Fibonacci). If you write only $F_0 = 0$ and the rule $F_n = F_{n-1} + F_{n-2}$, then $F_1$ is undefined and the sequence cannot be computed. Rule of thumb: the number of base cases equals the depth of the recursive reach. A two-step rule needs two base values; a three-step rule needs three.

What you now know

You can read and write recursive definitions, decide whether a recursion is well-defined (do the calls reach smaller arguments?), unwind a recursion to a numeric answer, and use induction to verify a guessed closed form. The next section, strong induction, gives you the proof tool that matches recursive definitions where the recursive clause reaches back more than one step at a time.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, §6.3.
• Knuth, D. E. (1997). The Art of Computer Programming, Vol. 1: Fundamental Algorithms (3rd ed.). Addison-Wesley, §1.2.8 (Fibonacci).
• Graham, R. L., Knuth, D. E., Patashnik, O. (1994). Concrete Mathematics (2nd ed.). Addison-Wesley, §6.6 (Fibonacci) and §1.1 (Hanoi).
• Wilf, H. S. (1994). generatingfunctionology. Academic Press, ch. 2.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press, ch. 4.