Secction

4.2. RECURSION, RECURRENCES AND INDUCTION

125

4.2

Recursion, Recurrences and Induction

Recursion

Exercise 4.2-1 Describe the uses you have made of recursion in writing programs. Include as many as you can. Exercise 4.2-2 Recall that in the Towers of Hanoi problem we have three pegs, and on one peg we have a stack of n disks, each smaller in diameter than the one below it. An allowable move consists of removing a disk from one peg and sliding it onto another peg so that it is not above another disk of smaller size. We are to determine how many allowable moves are needed to move the disks from one peg to another. Describe the strategy you used in a recursive program to solve this problem. For the Tower of Hanoi problem, you told the computer that to solve the problem with no disks you do nothing. To solve the problem of moving all disks to peg 2, you deal with the problem of moving n − 1 disks to peg 3, then move disk n to peg 2, and then deal with the problem of moving the n − 1 disks on peg 3 to peg 2. Thus if M (n) is the number of moves needed to move n disks from peg i to peg j, we have M (n) = 2M (n − 1) + 1. This is an example of a recurrence equation or recurrence. A recurrence equation is one that tells us how to compute the nth term of a sequence from the (n − 1)st term or some or all the preceding terms. To completely specify a function on the basis of a recurrence, we have to give enough information about the function to get started. This information is called the initial condition (or the initial conditions) for the recurrence. In this case we have said that M (0) = 0. Using this, we get from the recurrence that M (1) = 1, M (2) = 3, M (3) = 7, M (4) = 15, M (5) = 31, and are led to guess that M (n) = 2n − 1. Formally, we write our recurrence and initial condition together as M (n) = 0 if n = 0 2M (n − 1) + 1 otherwise (4.7)

Now we give an inductive proof that our guess is correct. The base case is trivial, as we have defined M (0) = 0,...