Application: Recursion and Induction

3.6. Application: Recursion and Induction#

In computer programming, there is a technique called recursion that is closely related to induction. In a computer program, a subroutine is a named sequence of instructions for performing a certain task. When that task needs to be performed in a program, the subroutine can be called by name. A typical way to organize a program is to break down a large task into smaller, simpler subtasks by calling subroutines to perform each of the subtasks. A subroutine can perform its task by calling other subroutines to perform subtasks of the overall task. A subroutine can also call itself. That is, in the process of performing some large task, a subroutine can call itself to perform a subtask. This is known as recursion, and a subroutine that does this is said to be a recursive subroutine. Recursion is appropriate when a large task can be broken into subtasks where some or all of the subtasks are smaller, simpler versions of the main task.

Application

Prolog is an example of a programming language that uses recursion to powerful effect. Classical Prolog has no loop construct: loops are defined using recursive subroutines.

Like induction, recursion is often considered to be a ‘hard’ topic by students. Experienced computer scientists, on the other hand, often say that they can’t see what all the fuss is about, since induction and recursion are elegant methods which ‘obviously’ work. In fairness, students have a point, since induction and recursion both manage to pull infinite rabbits out of very finite hats. But the magic is indeed elegant, and learning the trick is very worthwhile.

Application

In your course Computer Organisation you will be tasked to write a small recursive program to compute the factorial in Assembly. You can have a sneak-preview below of of what the pseudocode for such a program might be. In future courses like Algorithms & Data Structures and Algorithm Design you will also be tasked to write and analyse recursive algorithms.

3.6.1. Recursive factorials#

A simple example of a recursive subroutine is a function that computes $n!$ for a non-negative integer $n$. $n!$, which is read ‘’$n$ factorial’’, is defined as follows:

\[\begin{split}\begin{align*} 0! &= 1\\ n! &= \prod_{i=1}^n\,i\text{ for $n>0$}\\ \text{For example, }5! &=1\cdot2\cdot3\cdot4\cdot5=120. \text{ Note that for $n>1$,}\\ n! &= \prod_{i=1}^n\,i = \left(\prod_{i=1}^{n-1}\,i\right)\cdot n = \big((n-1)!\big)\cdot n\\ \end{align*}\end{split}\]

It is also true that $n!=\big((n-1)!\big)\cdot n$ when $n=1$. This observation makes it possible to write a recursive function to compute $n!$.

Application

All the programming examples in this section are written in the Java programming language. We won’t put these blue boxes around them.

int factorial( int n ) {
	// Compute n!.  Assume that n >= 0.
	int answer;
	if (n == 0) {
		answer = 1;
	} else {
		answer = factorial(n-1) * n;
	} 
	return answer;
}

To compute factorial($n$) for $n>0$, we can write a function (in Java). This function computes factorial($n-1$) first by calling itself recursively. The answer from that computation is then multiplied by $n$ to give the value of $n!$. The recursion has a base case, namely the case when $n=0$. For the base case, the answer is computed directly rather than by using recursion. The base case prevents the recursion from continuing forever, in an infinite chain of recursive calls.

Now, as it happens, recursion is not the best way to compute $n!$. It can be computed more efficiently using a loop. Furthermore, except for small values of $n$, the value of $n!$ is outside the range of numbers that can be represented as 32-bit ints. However, ignoring these problems, the factorial function provides a first example of the interplay between recursion and induction. We can use induction to prove that factorial($n$) does indeed compute $n!$ for $n\ge 0$.^[1]

Theorem 3.10

Assume that the data type int can represent arbitrarily large integers. Under this assumption, the factorial function defined above correctly computes $n!$ for any natural number $n$.

Proof. Let $P(n)$ be the statement ‘’ factorial ($n$) correctly computes $n!$’’. We use induction to prove that $P(n)$ is true for all natural numbers $n$.

Base case: In the case $n=0$, the if statement in the function assigns the value 1 to the answer. Since 1 is the correct value of $0!$, factorial (0) correctly computes $0!$.

Inductive case: Let $k$ be an arbitrary natural number, and assume that $P(k)$ is true. From this assumption, we must show that $P(k+1)$ is true. The assumption is that factorial($k$) correctly computes $k!$, and we want to show that factorial($k+1$) correctly computes $(k+1)!$.

When the function computes factorial($k+1$), the value of the parameter $n$ is $k+1$. Since $k+1>0$, the if statement in the function computes the value of factorial($k+1$) by applying the computation factorial$(k)*(k+1)$. We know, by the induction hypothesis, that the value computed by factorial($k$) is $k!$. It follows that the value computed by factorial($k+1$) is $(k!)\cdot(k+1)$. As we observed above, for any $k+1>0$, $(k!)\cdot(k+1)=(k+1)!$. We see that factorial ($k+1$) correctly computes $(k+1)!$. This completes the induction.

□

In this proof, we see that the base case of the induction corresponds to the base case of the recursion, while the inductive case corresponds to a recursive subroutine call. A recursive subroutine call, like the inductive case of an induction, reduces a problem to a ‘simpler’ or ‘smaller’ problem, which is closer to the base case.

3.6.2. Towers of Hanoi*#

Another standard example of recursion is the Towers of Hanoi problem. Let $n$ be a positive integer. Imagine a set of $n$ discs of decreasing size, piled up in order of size, with the largest disc on the bottom and the smallest disc on top. The problem is to move this tower of discs to a second pile, following certain rules: Only one disc can be moved at a time, and a disc can only be placed on top of another disc if the disc on top is smaller. While the discs are being moved from the first pile to the second pile, discs can be kept in a third, spare pile. All the discs must at all times be in one of the three piles.

Person

The Towers of Hanoi puzzle was first published by ‘Edouard Lucas in 1883. The puzzle is based on a legend of temple wherein there initially was one pile of discs neatly sorted from largest to smallest. In Lucas’s story, monks have since been continuously moving discs from this pile of 64 discs according to the rules of the puzzle to again created a sorted stack at the other end of the temple. It is said that when the last disc is placed, the world will end. But on the positive side, even if the monks move one disc every second, it will take approximately 42 times the age of the universe until they are done. And that is assuming they are using the optimal strategy…

Source: en.wikipedia.org/wiki/Tower_of_Hanoi

For example, if there are two discs, the problem can be solved by the following sequence of moves:

Move disc 1 from pile 1 to pile 3
Move disc 2 from pile 1 to pile 2
Move disc 1 from pile 3 to pile 2

A simple recursive subroutine can be used to write out the list of moves to solve the problem for any value of $n$. The recursion is based on the observation that for $n>1$, the problem can be solved as follows: Move $n-1$ discs from pile number 1 to pile number 3 (using pile number 2 as a spare). Then move the largest disc, disc number $n$, from pile number 1 to pile number 2. Finally, move the $n-1$ discs from pile number 3 to pile number 2, putting them on top of the $n^{th}$ disc (using pile number 1 as a spare). In both cases, the problem of moving $n-1$ discs is a smaller version of the original problem and so can be done by recursion. Here is the subroutine, written in Java:

void Hanoi(int n, int A, int B, int C) {
	// List the moves for moving n discs from
	// pile number A to pile number B, using
	// pile number C as a spare.  Assume n > 0.
	if (n == 1) {
		System.out.println("Move disc 1 from pile " + A + " to pile " + B);
	}
	else {
		Hanoi(n-1, A, C, B);
		System.out.println("Move disc " + n + " from pile " + 
		A + " to pile " + B);
		Hanoi(n-1, C, B, A);
	}
}

Note

This problem and its fame have led to implementations in a variety of languages, including a language called Brainf*ck.^[2] In the Computer Organisation course, you can implement an interpreter for this language and test it on the implementation of the Hanoi algorithm.

We can use induction to prove that this subroutine does in fact solve the Towers of Hanoi problem.

Theorem 3.11

The sequence of moves printed by the Hanoi subroutine as given above correctly solves the Towers of Hanoi problem for any integer $n\ge1$.

Proof. We prove by induction that whenever $n$ is a positive integer and $A$, $B$, and $C$ are the numbers 1, 2, and 3 in some order, the subroutine call Hanoi($n,A,B,C$) prints a sequence of moves that will move $n$ discs from pile $A$ to pile $B$, following all the rules of the Towers of Hanoi problem.

In the base case, $n=1$, the subroutine call Hanoi($1,A,B,C$) prints out the single step ‘’Move disc 1 from pile A to pile B’’, and this move does solve the problem for 1 disc.

Let $k$ be an arbitrary positive integer, and suppose that Hanoi($k,A,B,C$) correctly solves the problem of moving the $k$ discs from pile $A$ to pile $B$ using pile $C$ as the spare, whenever $A$, $B$, and $C$ are the numbers 1, 2, and 3 in some order. We need to show that Hanoi($k+1,A,B,C$) correctly solves the problem for $k+1$ discs. Since $k+1>1$, Hanoi ($k+1,A,B,C$) begins by calling Hanoi($k,A,C,B$). By the induction hypothesis, this correctly moves $k$ discs from pile $A$ to pile $C$. disc number $k+1$ is not moved during this process. At that point, pile $C$ contains the $k$ smallest discs and pile $A$ still contains the $(k+1)^{st}$ disc, which has not yet been moved. So the next move printed by the subroutine, ‘’Move disc $(k+1)$ from pile A to pile B’’, is legal because pile $B$ is empty. Finally, the subroutine calls Hanoi($k,C,B,A$), which, by the induction hypothesis, correctly moves the $k$ smallest discs from pile $C$ to pile $B$, putting them on top of the $(k+1)^{\text{st}}$ disc, which does not move during this process. At that point, all $(k+1)$ discs are on pile $B$, so the problem for $k+1$ discs has been correctly solved.

□

3.6.3. Exercises#

Exercise (1)

The Hanoi subroutine given in this section does not just solve the Towers of Hanoi problem. It solves the problem using the minimum possible number of moves. Use induction to prove this fact.

Exercise (2)

Use induction to prove that the Hanoi subroutine uses $2^n-1$ moves to solve the Towers of Hanoi problem for $n$ discs.

Exercise (3)

Consider the following recursive function:

int power(int x, int n) {
	// Compute x raised to the power n.
	// Assume that n >= 0.
	int answer;
	if (n == 0) {
		answer = 1;
	} else if (n % 2 == 0) {
		answer = power(x * x, n / 2);
	} else {
		answer = x * power(x * x, (n-1) / 2);
	}
	return answer;
}

Show that for any integer $x$ and any non-negative integer $n$, the function power($x$,$n$) correctly computes the value of $x^n$. (Assume that the int data type can represent arbitrarily large integers.) Note that the test ‘’if (n % 2 == 0)’’ tests whether $n$ is evenly divisible by 2. That is, the test is true if $n$ is an even number. (This function is actually a very efficient way to compute $x^n$.)

Application: Recursion and Induction

Contents

3.6. Application: Recursion and Induction#

3.6.1. Recursive factorials#

3.6.2. Towers of Hanoi*#

3.6.3. Exercises#