Section1.9: Application: Recursion and Induction
 Page ID
 7466
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.
Like induction, recursion is often considered to be a “hard” topic by students. Professors, 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.
A simple example of a recursive subroutine is a function that computesn! for a nonnegative integer n. n!, which is read “n factorial,” is defined as follows:
\[0! =1 \nonumber\]
\[n! = \Pi_{i=1}^{n} i \text{ for } n>0 \nonumber\]
Forexample,\(5!=1·2·3·4·5=120\). Note that for \(n>1\),
\[n! = \Pi_{i=1}^{n} i= (\Pi_{i=1}^{n1} i) \cdot n = ((n1)!) \cdot n \nonumber\]
It is also true that \(n! = ((n−1)!)·n\) when \(n = 1\). This observation makes it possible to write a recursive function to compute \(n!\). (All the programming examples in this section are written in the Java programming language.)
int factorial( int n ) { // Compute n!. Assume that n >= 0. int answer; if ( n == 0 ) { answer = 1; } else { answer = factorial( n1 ) * n; } return answer; }
In order to compute \(factorial(n)\) for \(n > 0\), this function first computes \(factorial (n − 1)\) 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 32bit ints. However, ignoring these problems, the factorial function provides a nice first example of the interplay between recursion and induction. We can use induction to prove that \(factorial(n)\) does indeed compute \(n!\) for \(n ≥ 0\). (In the proof, we pretend that the data type int is not limited to 32 bits. In reality, the function only gives the correct answer when the answer can be represented as a 32bit binary number.)
Theorem 1.14
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 parametern 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!)·(k+1)\). As we observed above, for any \(k+1 > 0, (k!)·(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.
Another standard example of recursion is the Towers of Hanoi problem. Let \(n\) be a positive integer. Imagine a set of n disks of decreasing size, piled up in order of size, with the largest disk on the bottom and the smallest disk on top. The problem is to move this tower of disks to a second pile, following certain rules: Only one disk can be moved at a time, and a disk can only be placed on top of another disk if the disk on top is smaller. While the disks are being moved from the first pile to the second pile, disks can be kept in a third, spare pile. All the disks must at all times be in one of the three piles. For example, if there are two disks, the problem can be solved by the following sequence of moves:
Move disk 1 from pile 1 to pile 3 Move disk 2 from pile 1 to pile 2 Move disk 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\) disks from pile number 1 to pile number 3 (using pile number 2 as a spare). Then move the largest disk, disk number n, from pile number 1 to pile number 2. Finally, move the \(n − 1\) disks from pile number 3 to pile number 2, putting them on top of the nth disk (using pile number 1 as a spare). In both cases, the problem of moving \(n − 1\) disks 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 disks 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 disk 1 from pile " + A + " to pile " + B); } else { Hanoi( n1, A, C, B ); System.out.println("Move disk " + n + " from pile " + A + " to pile " + B); Hanoi( n1, C, B, A ); } }
We can use induction to prove that this subroutine does in fact solve the Towers of Hanoi problem.
Theorem 1.15
The sequence of moves printed by the Hanoi subroutine as given above correctly solves the Towers of Hanoi problem for any integer \(n ≥ 1\).
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\) disks 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 disk 1 from pile \(A\) to pile \(B\),” and this move does solve the problem for 1 disk.
Let \(k\) be an arbitrary positive integer, and suppose that \(Hanoi(k, A, B, C)\) correctly solves the problem of moving the \(k\) disks 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\) disks. 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\) disks from pile \(A\) to pile \(C\). Disk number \(k+1\) is not moved during this process. At that point, pile \(C\) contains the \(k\) smallest disks and pile \(A\) still contains the \((k + 1)^{st}\) disk, which has not yet been moved. So the next move printed by the subroutine, “Move disk \((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 disks from pile \(C\) to pile \(B\), putting them on top of the \((k + 1)^{st}\) disk, which does not move during this process. At that point, all \((k + 1)\) disks are on pile \(B\), so the problem for \(k + 1\) disks has been correctly solved.
Recursion is often used with linked data structures, which are data structures that are constructed by linking several objects of the same type together with pointers. (If you don’t already know about objects and pointers, you will not be able to follow the rest of this section.) For an example, we’ll look at the data structure known as a binary tree. A binary tree consists of nodes linked together in a treelike structure. The nodes can contain any type of data, but we will consider binary trees in which each node contains an integer. A binary tree can be empty, or it can consist of a node (called the root of the tree) and two smaller binary trees (called the left subtree and the right subtree of the tree). You can already see the recursive structure: A tree can contain smaller trees. In Java, the nodes of a tree can be represented by objects belonging to the class
class BinaryTreeNode { int item; // An integer value stored in the node. BinaryTreeNode left; // Pointer to left subtree. BinaryTreeNode right; // Pointer to right subtree. }
An empty tree is represented by a pointer that has the special value null. If root is a pointer to the root node of a tree, then root.left is a pointer to the left subtree and root.right is a pointer to the right subtree. Of course, both root.left and root.right can be null if the corresponding subtree is empty. Similarly, root.item is a name for the integer in the root node.
Let’s say that we want a function that will find the sum of all the integers in all the nodes of a binary tree. We can do this with a simple recursive function. The base case of the recursion is an empty tree. Since there are no integers in an empty tree, the sum of the integers in an empty tree is zero. For a nonempty tree, we can use recursion to find the sums of the integers in the left and right subtrees, and then add those sums to the integer in the root node of the tree. In Java, this can be expressed as follows:
The ideal gas law is easy to remember and apply in solving problems, as long as you get the proper values a
int TreeSum( BinaryTreeNode root ) { // Find the sum of all the integers in the // tree that has the given root. int answer; if(root==null){ //Thetreeisempty. answer = 0; } else { answer = TreeSum( root.left ); answer = answer + TreeSum( root.right ); answer = answer + root.item; } return answer; }
We can use the second form of the principle of mathematical induction to prove that this function is correct.
Theorem 1.16
The function TreeSum, defined above, correctly computes the sum of all the integers in a binary tree.
Proof. We use induction on the number of nodes in the tree. Let \(P(n)\) be the statement “TreeSum correctly computes the sum of the nodes in any binary tree that contains exactly n nodes.” We show that \(P(n)\) is true for every natural number \(n\).
Consider the case \(n = 0\). A tree with zero nodes is empty, and an empty tree is represented by a null pointer. In this case, the if statement in the definition of TreeSum assigns the value 0 to the answer, and this is the correct sum for an empty tree. So, \(P(0)\) is true.
Let \(k\) be an arbitrary natural number, with \(k > 0\). Suppose we already know \(P(x)\) for each natural number \(x\) with \(0 ≤ x < k\). That is, TreeSumcorrectly computes the sum of all the integers in any tree that has fewer than \(k\) nodes. We must show that it follows that \(P(k)\) is true, that is, that TreeSum works for a tree with \(k\) nodes. Suppose that root is a pointer to the root node of a tree that has a total of \(k\) nodes. Since the root node counts as a node, that leaves a total of \(k − 1\) nodes for the left and right subtrees, so each subtree must contain fewer than k nodes. By the induction hypothesis, we know that TreeSum(root.left) correctly computes the sum of all the integers in the left subtree, and TreeSum(root.right) correctly computes the sum of all the integers in the right subtree. The sum of all the integers in the tree is root.item plus the sums of the integers in the subtrees, and this is the value computed by TreeSum. So, TreeSum does work for a tree with \(k\) nodes. This completes the induction.
Note how closely the structure of the inductive proof follows the struc ture of the recursive function. In particular, the second principle of math ematical induction is very natural here, since the size of subtree could be anything up to one less than the size of the complete tree. It would be very difficult to use the first principle of induction in a proof about binary trees.
Exercises

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.

Use induction to prove that the Hanoi subroutine uses \(2^{n} − 1\) moves to solve the Towers of Hanoi problem for \(n\) disks. (There is a story that goes along with the Towers of Hanoi problem. It is said that on the day the world was created, a group of monks in Hanoi were set the task of solving the problem for 64 disks. They can move just one disk each day. On the day the problem is solved, the world will end. However, we shouldn’t worry too much, since \(2_{64} − 1 \) days is a very long time—about 50 million billion years.)

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, (n1) / 2); } return answer; }
Show that for any integer \(x\) and any nonnegative 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 nis an even number. (This function is actually a very efficient way to compute \(x^{n}\) .)
4. A leaf node in a binary tree is a node in which both the left and the right subtrees are empty. Prove that the following recursive function correctly counts the number of leaves in a binary tree:
int LeafCount( BinaryTreeNode root ) { // Counts the number of leaf nodes in // the tree with the specified root. int count; if ( root == null ) { count = 0; } else if ( root.left == null && root.right == null ) { count = 1; } else { count = LeafCount( root.left ); count = count + LeafCount( root.right ); } return count; }
5. A binary sort tree satisfies the following property: If node is a pointer to any node in the tree, then all the integers in the left subtree of node are less than node.item and all the integers in the right subtree of node are greater than or equal to node.item. Prove that the following recursive subroutine prints all the integers in a binary sort tree in nondecreasing order:
void SortPrint( BinaryTreeNode root ) { // Assume that root is a pointer to the // root node of a binary sort tree. This // subroutine prints the integers in the // tree in nondecreasing order. if ( root == null ) { // There is nothing to print. } else { SortPrint( root.left ); System.out.println( root.item ); SortPrint( root.right ); } }