Discrete Math › Section E · Sequences › Topic E.7

Recursion and structural induction

Recursion defines a thing in terms of smaller versions of itself: a number, a set of strings, or an algorithm that calls itself. Structural induction is the matching proof method, and together they explain why recursive programs work and how long they take.

Defining by self-reference

A recursive definition has a base case that needs no further work and a rule that builds new values from smaller ones. Factorial is the standard example: \(0! = 1\), and \(n! = n \cdot (n-1)!\) for \(n \ge 1\). So 4! = 4 · 3! = 4 · 3 · 2! and so on, down to 24. The Fibonacci numbers, with \(F_0 = 0\), \(F_1 = 1\) and \(F_n = F_{n-1} + F_{n-2}\), are another. The recursive definitions of sequences in "Describing sequences and sums" are all of this kind. Without a base case the definition never bottoms out, and it defines nothing.

Recursively defined sets

Sets can be built the same way, with base elements and construction rules, plus the understanding that nothing else belongs. Take the balanced bracket strings: the empty string is balanced; if \(s\) is balanced, so is \((s)\); and if \(s\) and \(t\) are balanced, so is the joined string \(st\). From these rules come \(()\), \(()()\), \((())\) and \((()())\), but never \()(\). Arithmetic expressions, file systems of folders inside folders, and the grammar of programming languages are all defined like this. A simpler numeric example: let 2 be in \(S\), and whenever \(x\) is in \(S\), let \(x + 5\) be in \(S\). Then \(S = \{2, 7, 12, 17, \ldots\}\).

Structural induction

To prove that every element of a recursively defined set has some property, use structural induction. First, show that each base element has the property. Second, show that each construction rule preserves it: if the elements a rule starts from have the property, so does the element it builds. Since every element is made by finitely many applications of the rules, every element has the property. This is ordinary induction in disguise, on the number of rule applications, but it follows the shape of the definition instead of the integers. For the set \(S\) above, every element leaves remainder 2 on division by 5: true for 2, and adding 5 keeps the remainder.

Worked example: balanced brackets

Prove that every balanced bracket string has equally many opening and closing brackets. 1. Base element: the empty string has 0 of each. 2. Wrapping rule: suppose \(s\) has \(m\) of each. Then \((s)\) has \(m + 1\) opening and \(m + 1\) closing brackets. 3. Joining rule: suppose \(s\) has \(m\) of each and \(t\) has \(p\) of each. Then \(st\) has \(m + p\) of each. 4. Every rule preserves the property, so by structural induction every balanced string has it. The converse is false: \()(\) has one of each but is not balanced. Equal counts are necessary, not sufficient.

Recursive algorithms

A recursive algorithm solves a problem by calling itself on smaller inputs until it reaches a base case it can answer directly. Computing \(n!\) recursively multiplies \(n\) by the answer for \(n - 1\), stopping at \(0! = 1\). Binary search looks at the middle item of a sorted list and then searches only the half that could contain the target. Merge sort splits a list in two, sorts each half recursively and merges the sorted halves. Each call must make the input strictly smaller, or the recursion never reaches its base case.

Worked example: the Towers of Hanoi

Three pegs hold \(n\) discs of different sizes, stacked largest at the bottom. Move the whole stack to another peg, one disc at a time, never putting a larger disc on a smaller one. 1. Recursive plan: move the top \(n - 1\) discs to the spare peg, move the largest disc, then move the \(n - 1\) discs on top of it. 2. Count: \(T_n = 2T_{n-1} + 1\) with \(T_1 = 1\), so 1, 3, 7, 15, 31. 3. No method does better: the largest disc must move at least once, and before its first move the other \(n - 1\) discs must all be stacked on one other peg, taking at least \(T_{n-1}\) moves, and after its last move they must be restacked on it, taking \(T_{n-1}\) more. 4. The topic "Exponential sequences and solving recurrences" solved this to \(T_n = 2^n - 1\). For 64 discs at one move per second, that is about 585 billion years.

Correctness by induction

Recursive algorithms are proved correct by strong induction on the size of the input, following the topic "Strong induction". The base case checks that the algorithm answers the smallest inputs correctly. The inductive step assumes that every recursive call on a smaller input returns the right answer, and shows that the algorithm combines those answers correctly. For merge sort: a list of length 0 or 1 is already sorted; and if both halves come back sorted, merging two sorted lists gives a sorted list. The proof has exactly the same structure as the algorithm, which is why recursion and induction are taught together.

Worked example: the cost of naive recursion

Computing \(F_n\) straight from the definition, by calling the function on \(n - 1\) and \(n - 2\), is correct but slow. 1. Let \(C_n\) be the number of calls made. Then \(C_0 = C_1 = 1\) and \(C_n = C_{n-1} + C_{n-2} + 1\). 2. This gives 1, 1, 3, 5, 9, 15 for \(n = 0\) to 5, and in fact \(C_n = 2F_{n+1} - 1\). 3. For \(n = 30\) that is 2 × 1,346,269 − 1 = 2,692,537 calls to find \(F_{30} = 832{,}040\). 4. The waste comes from recomputing the same values again and again: \(F_{28}\) is computed twice, \(F_{27}\) three times, and so on.

Recursion and iteration

Any recursive algorithm can be rewritten with a loop, and the reverse is also true. Recursion is usually clearer for naturally recursive structures, such as trees, nested expressions and divide-and-conquer methods. Loops avoid the memory each pending call uses. The Fibonacci waste has two standard cures. Memoisation stores each value the first time it is computed and looks it up afterwards, so each \(F_k\) is computed once. Or iterate: keep the last two values and step forwards, which takes about \(n\) additions and almost no memory.

Common mistakes to avoid

First, a missing or unreachable base case, which makes the recursion run until the program runs out of memory for pending calls, a stack overflow. Second, recursive calls that do not shrink the input, such as calling on \(n\) again instead of \(n - 1\). Third, off-by-one base cases: Fibonacci needs both \(F_0\) and \(F_1\). Fourth, forgetting a construction rule in a structural induction proof; every rule must be checked. Fifth, ignoring repeated work, which can turn a linear task into an exponential one.

Key takeaways

Recursive definitions give base cases and rules that build larger objects from smaller ones, for numbers, sets and algorithms alike. Structural induction proves a property for a recursively defined set by checking the base elements and showing each rule preserves the property. Recursive algorithms call themselves on smaller inputs and are proved correct by strong induction on input size. The Towers of Hanoi need \(2^n - 1\) moves. Naive recursive Fibonacci makes \(2F_{n+1} - 1\) calls; memoisation or iteration removes the waste.

Flashcards

Flashcard

Recursive definition

Base cases plus a rule built from smaller cases

0! = 1 and n! = n·(n − 1)!.

Test your understanding

Question 1 of 5

How many moves does the Towers of Hanoi puzzle need with 5 discs?

Question 2 of 5

To prove by structural induction that every element of a recursively defined set has a property, what must you show?

Question 3 of 5

Let 2 be in S, and whenever x is in S let x + 5 be in S, with nothing else in S. Which number is in S?

Question 4 of 5

A recursive function has no base case. What happens when it is called?

Question 5 of 5

Why is computing Fₙ directly from Fₙ = Fₙ₋₁ + Fₙ₋₂ by naive recursion so slow?

← Previous topicNext topic →