Page 824 - Introduction to Programming with Java: A Problem Solving Approach

790 Appendix 8 Recursion Towers of Hanoi Problem
Now it’s time for a problem that would be very hard to solve with loops—where recursion is unquestionably the best way to go. Imagine you are a medieval lord who oversees a group of bored monks. To keep them busy on rainy days, you have them solve the Towers of Hanoi problem. There are three locations “A,” “B,” and “C.” Initially, there is a stack of disks at location “A.” The smallest disk is on the top, and disk diam- eter increases as you go down toward the base of the “tower.” Locations “B” and “C” are initially empty. Figure A8.6 shows what it looks like when the 4-disk-high tower sits at location “A”:
Figure A8.6 Setup for Towers of Hanoi problem
Apago PDF Enhancer
Your monks are to move the tower of disks from location A to location C, always obeying these rules:
• Moveonlyonediskatatime.
• Neverplaceanydiskontopofasmallerdisk.
Your task is to come up with a simple algorithm for how to solve this problem. If you had to do it with loops, it would be a mess. But if you use recursion, it’s reasonably simple. Whenever you want to make a move, you have a source location, s, you have a destination location, d, and you have a temporary location, t. For our overall goal, s is A, d is C, and t is B. As you progress toward the final solution, you’ll have subordinate goals, with different locations for s, d, and t. Here is the general algorithm. It applies to any subset of disks from disk n down to disk 1, where n is any number from the maximum number of disks down to 1:
• Movethegroupofdisksabovedisknfromstot.
• Movediskntod.
• Move the group of disks previously above disk n from t to d.
Figure A8.7 shows an example of this algorithm in action. (This particular example happens to be the last few steps in the final solution.) The configuration on the left is a condition that exists shortly before the goal is attained. The configuration on the right is the final condition. The dashed arrows indicate each of the three operations described above for the simplest non-trivial case where there is only one disk above disk 2. The trivial case is the stopping condition. It’s when you move the top disk, disk 1, from a source location to a destination location. An example of this appears as the last step in Figure A8.7. This happens to be the final stopping condition, but as you’ll see, a program that solves the Towers of Hanoi problem will hit the stop- ping condition and automatically re-start many times during its execution.
1
⎫
⎪
⎪
⎪
⎬ disk ⎪
⎪ ⎪ ⎭
2
3
4
locations
ABC