Recursion is the process of defining an element in a succession based on the prior elements in the sequence. In computer science, we speak of recursive algorithms, functions, and subroutines. A common example of a recursive function is the factorial function !, in which n! is defined as n*(n-1)!. In order for such algorithms to work, however, there must be some stopping point. For example, when computing factorial, we define 1!=1, and there is no need to recurse further. Without this base case, the process would go on until the computer ran out of memory and returned an error. In order to be sure that the algorithm ends, we must be sure that the recursive part of the algorithm approaches the base case. A recursive algorithm to compute n! is as follows.
int factorial(int n)
{
if (n == 1)
return 1;
return n * factorial(n-1);
}
In an ancient city, so the legend goes, monks in a temple had to move a pile of 64 sacred disks from one location to another. The disks were fragile; only one could be carried at a time. A disk could not be placed on top of a smaller, less valuable disk. In addition, there was only one other location in the temple (besides the original and destination locations) sacred enough for a pile of disks to be placed there.
Using the intermediate location, the monks began to move disks back and forth from the original pile to the pile at the new location, always keeping the piles in order (largest on the bottom, smallest on the top). According to the legend, before the monks could make the final move to complete the new pile in the new location, the temple would turn to dust and the world would end.
Is there any truth to this legend?
There is a game based on this legend. You have three posts onto which you can put the disks, which have holes in the center. The disks all start on the leftmost post and you want to move them to the rightmost post, never putting a disk on top of a smaller one. The center post is for intermediate storage.
You are given a subroutine MoveSingleDisc(int from, int to, int aux) that removes one disk from the tower whose number is the first argument to the tower whose number is the second argument. The third argument (aux) indicates the tower used for intermediate storage. The towers are numbered left to right as 0, 1, 2. Note that the towers are numbered, but the disks are not. Do not attempt to label the disks in any way! For example, MoveSingleDisc(0,2,1) moves a disk from tower 0 and puts it on tower 2.
Suppose there is only one disc on the leftmost tower. We can solve the Towers of Hanoi with one call to MoveSingleDisc:
MoveSingleDisc(0,2,1);
If there are two disks on the leftmost tower, the following algorithm will solve the Towers of Hanoi with three calls to MoveSingleDisc:
MoveTwoDisks()
{
MoveSingleDisc(0,1,2);
MoveSingleDisc(0,2,1);
MoveSingleDisc(1,2,0);
}
Suppose we don't know the location of the original tower. Then we can rewrite our algorithm to take as input the arguments from, to, and aux:
MoveTwoDisks(int from, int to, int aux)
{
MoveSingleDisc(from,to,aux);
MoveSingleDisc(from,aux,to);
MoveSingleDisc(to,aux,from);
}
Problem 1: Suppose there are three disks on the leftmost tower. Write an algorithm MoveThreeDisks() to solve the Towers of Hanoi. How many calls to MoveSingleDisc are required? Justify your answer.
Problem 2: Suppose there are four disks on the leftmost tower. Write an algorithm MoveFourDisks() to solve the Towers of Hanoi. How many calls to MoveSingleDisc are required? Justify your answer.
Problem 3: Suppose there are n disks on the leftmost tower, where n is a positive integer. How many calls to MoveSingleDisc are required to solve the Towers of Hanoi? Justify your answer. (Hint: Your answer should be in terms of n)