Skip to main content

Section 4.1 Introduction to recursion

Definition 4.1.1.

A process is recursive if it is executed recursively.

Just kidding. That joke will make more sense at the end of this chapter. Here is a better definition of recursion.

Definition 4.1.2.

A process is recursive if it is executed by executing itself.

Recursive objects, definitions, functions, and processes are central to mathematics and computer science, and they will appear several times in the rest of this book. As you have seen, recursion can be awkward to define. Consider the following examples of recursive structures.

The set of natural numbers \(\mathbb{N}\) can be defined recursively:

  • The first natural number is \(0\text{.}\) (Or \(1\text{,}\) if you insist.)

  • If \(n\) is a natural number, then so is \(n+1\text{.}\)

Because \(0\) is a natural number, then so is \(0+1=1\text{,}\) and \(1+1=2\text{,}\) etc. We can generate all the natural numbers recursively starting with 0.

All recursive definitions involve a “base case,” somewhere to start. Without a base case the recursive definition would “descend forever” and not be of any practical use.

In the next chapter we will learn about sequences. Whatever those are, two of them are famously recursive: the sequence of factorials and the sequence of Fibonacci numbers.

The sequence of factorials, whose terms are denoted \(n!\text{,}\) is defined so that \(0!=1\) and thereafter \(n!=n(n-1)!\text{.}\) So, therefore, the next few factorials are \(1!=1(0!)=1\text{,}\) \(2!=2(1!)=2\text{,}\) \(3!=3(2!)=6\text{,}\) and \(4!=4(3!)=24\text{.}\)

The sequence of Fibonacci numbers is defined such that every Fibonacci number is the sum of the two before it. We start with \(F_0 = 1\) and \(F_1 = 1\) and then define \(F_n = F_{n-1} + F_{n-2}\text{.}\) Therefore the next few are \(2\text{,}\) \(3\text{,}\) \(5\text{,}\) and \(8\text{.}\)

The Tower of Hanoi is a famous logic puzzle. There are three poles and \(n\) discs that must be moved from the first pole to the third. One disc may be moved at a time, and a disc may only be placed on top of a smaller disc. What is the minimum number of moves required to complete a Tower of Hanoi puzzle? We won't spoil that answer, but it turns out the solution is recursive. You proceed by moving \((n-1)\) discs to the second pole, then moving the largest disc to the third pole, and then moving the \((n-1)\) discs on top of the largest disc. So, you play a Tower of Hanoi game by playing two smaller Tower of Hanoi games.

An animation showing a solution to the game can be found here.

Another recursive process is the process of representing an integer in another base, or number system. Perhaps you have heard of binary numbers. In the next section, we will learn how to recursively represent any natural number in the base-\(2\) number system.