Recursive definitions and algorithms
Recursion defines something in terms of smaller versions of itself. It is a powerful way to describe sequences, structures, and algorithms.
Recursive definitions
A recursive definition has a base case and a rule building new values from old ones. Factorial: \(0! = 1\) and \(n! = n \cdot (n-1)!\). Fibonacci: \(F_0 = 0\), \(F_1 = 1\), \(F_n = F_{n-1} + F_{n-2}\). Without a base case, the definition never bottoms out.
Recursively defined sets
Sets can be defined recursively too. The set of well-formed bracket strings: the empty string is balanced; if \(s\) is balanced, so is \((s)\); if \(s\) and \(t\) are balanced, so is \(st\). Programming languages, file systems, and arithmetic expressions are all defined this way.
Structural induction
To prove a property of a recursively defined set, use structural induction: show it holds for the base elements and is preserved by each construction rule. For balanced brackets, every string has equally many open and close brackets: true for the empty string, and preserved by wrapping and concatenating.
Recursive algorithms
A recursive algorithm solves a problem by calling itself on smaller inputs. Computing \(n!\) recursively multiplies \(n\) by the result for \(n - 1\). Binary search checks the middle of a sorted list and recurses on one half. Merge sort splits a list, sorts each half recursively, and merges the results.
Worked example: towers of Hanoi
Move \(n\) discs from one peg to another, never placing a larger disc on a smaller one. Recursively: move \(n - 1\) discs aside, move the largest, then move the \(n - 1\) back on top. The move count satisfies \(T_n = 2T_{n-1} + 1\), \(T_1 = 1\), giving \(T_n = 2^n - 1\). Sixty-four discs would take over 500 billion years at one move per second.
T_n = 2T_{n-1} + 1 \Rightarrow T_n = 2^n - 1Recursion versus iteration
Any recursion can be rewritten as a loop, and vice versa. Recursion is often clearer for naturally recursive structures like trees, while loops can be more efficient. Naive recursive Fibonacci recomputes the same values exponentially often; storing results (memoisation) or iterating fixes this.
Correctness by induction
Recursive algorithms are proved correct by induction on the input size: the base case returns the right answer, and if the recursive calls on smaller inputs are correct, combining them gives a correct answer. This is exactly the structure of the algorithm itself.
Common mistakes
Forgetting the base case, causing infinite recursion. Recursive calls that do not shrink the problem. Inefficient repeated computation. Off-by-one errors in base cases.
Key takeaways
Recursive definitions need base cases and building rules. Structural induction proves properties of recursively defined sets. Recursive algorithms call themselves on smaller inputs and are proved correct by induction. Memoisation avoids repeated work.
Flashcard
Base case plus a rule using earlier values
Check your understanding
How many moves does the Towers of Hanoi puzzle need for 4 discs?