Welcome to Recursion Lab 4. In this lab you will be introduced, via pseudo code, the algorithm behind the Towers of Hanoi application. Please keep in mind while you are going through this lab that it only deals with the recursive portion of the application.

Before we begin, let’s stop and take a look at the problem. For those of you who are unfamiliar with Towers of Hanoi it is a game which deals with moving a stack of disks from the starting tower to the destination tower one at a time using the intermediate tower to aid you in this process. If you have never played Towers of Hanoi, this URL, http://javascript.internet.com/games/hanoi.html will allow you to play the game; I highly recommend doing this if you never have played the game, to become familiar with the way it works.

Before we start pseudo programming the recursive part of this application let’s stop and think about what is entailed in this task. First, you will have three towers between which you need to move the disks. In addition, you must move the disks one at a time and you cannot stack a larger disk on top of a smaller disk. To move the disks, you must first move all but the bottom disk to the intermediate tower. Then you need to move the bottom disk onto the destination tower and then stack the rest of the disks on top. Now that you know what moving the disks entails, you need to ask yourself, “How can this be done?” As stated, you will first need to take all of the disks except the first and put them on the intermediate tower so that you can get to the last disk, but the catch is, you can only move one at a time and cannot stack a larger disk on top of a smaller disk. So what you will need to do is move all the disks above the second to last disk; however you cannot move that disk until you move the disks that are above it. So you keep going through these steps till you get to the first disk. Graphically this would look similar to the following diagram:

Now that you have reached a disk that you can move, you need to move it to the ending tower. Once you move the top disk on to the its destination tower, you are able to move the second disk to the intermediate tower and then move the top disk on top of it, thus moving all but the bottom disk to the intermediate tower, as shown below:

Once you reach this point you can now move the bottom disk to the destination tower. and going through the same steps as above get the two disks that are on the intermediate tower on top of the last disk and thus on the destination tower.  Each of the successive steps should look similar to the below graphical examples:

Now that we know how we need to move the disks around it is time to code the Towers of Hanoi recursive section of the application.  First, we will need to determine what our terminating condition will be.  In this case, we want the terminating condition to be that there are no more disks above the one we are currently trying to move.  That means that before you move a disk, you must ensure that there are no disks above the one you want to move.  If there are, you need to recall the procedure and subtract 1 from the height at which you are going to work. Furthermore, you will need to flip-flop the destination tower and the intermediate tower since you need to leave a tower open for the disk below the one you are presently working with.  Then, once you get to the point where there are no more disks above the one you are presently working on, you can move that disk. Once you move that disk, you can move down the line of procedure code to move on to the next step. For example, you are using 3 disks. You would call the procedure that deals with determining which disk to move by passing it the height of the disks on the tower (in this case 3), the starting tower (A), the intermediate tower (B), and the destination tower (C).  After you call this procedure, it checks for disks above the one that it is looking at (when the procedure starts it is always looking at the bottom disk).  If there are any disks on top of the disk you are working with, the procedure needs to recall itself, flip-flopping the intermediate tower and the ending tower, and subtracting 1 from the disk you are working on. The following example demonstrates this:

Is 3 >= 1 Yes Call the procedure again passing it 2, Starting tower still the same (A), Intermediate tower now ending tower (B), ending tower now intermediate tower (C).

After that execution is complete, it moves on to the next recursive iteration.

Is 3 >= 1 Yes Call the procedure again passing it 2, Starting tower still the same (A), Intermediate tower now ending tower (B), ending tower now intermediate tower (C). Is 2 >= 1 Yes Call the procedure again passing it 1, Starting tower still the same (A), Intermediate tower now ending tower (C), ending tower now intermediate tower (B).