21.11. Review Questions

[Page 643 ( continued )]

19.6. Tower of Hanoi

The Tower of Hanoi problem is another classic recursion example. The problem can be solved easily using recursion, but is difficult to solve without using recursion.

The problem involves moving a specified number of disks of distinct sizes from one tower to another while observing the following rules:

• There are n disks labeled 1, 2, 3, , n , and three towers labeled A, B, and C.

• No disk can be on top of a smaller disk at any time.

• All the disks are initially placed on tower A.

• Only one disk can be moved at a time, and it must be the top disk on the tower.

The objective of the problem is to move all the disks from A to B with the assistance of C. For example, if you have three disks, as shown in Figure 19.4, the following steps will move all of the disks from A to B:

1.	Move disk 1 from A to B.
2.	Move disk 2 from A to C.
[Page 644]
3.	Move disk 1 from B to C.
4.	Move disk 3 from A to B.
5.	Move disk 1 from C to A.
6.	Move disk 2 from C to B.
7.	Move disk 1 from A to B.

Figure 19.4. The goal of the Towers of Hanoi problem is to move disks from tower A to tower B without breaking the rules.

Note

The Towers of Hanoi is a classic computer science problem. There are many Websites devoted to this problem. The Website www.cut-the-knot.com/ recurrence /hanoi.html is worth seeing.

In the case of three disks, you can find the solution manually. However, the problem is quite complex for a larger number of disks ”even for four. Fortunately, the problem has an inherently recursive nature, which leads to a straightforward recursive solution.

The base case for the problem is n = 1 . If n == 1 , you could simply move the disk from A to B. When n > 1 , you could split the original problem into three subproblems and solve them sequentially.

1.	Move the first n - 1 disks from A to C with the assistance of tower B.
2.	Move disk n from A to B.
3.	Move n - 1 disks from C to B with the assistance of tower A.

---

[Page 645]

The following method moves n disks from the fromTower to the toTower with the assistance of the auxTower :

   void   moveDisks(   int   n,   char   fromTower,   char   toTower,   char   auxTower) 

The algorithm for the method can be described as follows :

   if   (n ==   1   )  // Stopping condition  Move disk   1   from the fromTower to the toTower;   else   { moveDisks(n -   1   , fromTower, auxTower, toTower); Move disk n from the fromTower to the toTower; moveDisks(n -   1   , auxTower, toTower, fromTower); } 

Listing 19.7 gives a program that prompts the user to enter the number of disks and invokes the recursive method moveDisks to display the solution for moving the disks. A sample run of the following program appears in Figure 19.5.

Figure 19.5. The program prompts the user to enter the number of disks and then displays the steps that must be followed to solve the Towers of Hanoi problem.

Listing 19.7. TowersOfHanoi.java

(This item is displayed on pages 645 - 646 in the print version)

 1   import   javax.swing.JOptionPane; 2 3   public class   TowersOfHanoi { 4  /** Main method */  5   public static void   main(String[] args) { 6  // Read number of disks, n  7 String intString = JOptionPane.showInputDialog( 8   "Enter number of disks:"   ); 9 10  // Convert string into integer  11   int   n = Integer.parseInt(intString); 12 13  // Find the solution recursively  14 System.out.println(   "The moves are:"   ); 15  moveDisks(n,   'A'   ,   'B'   ,   'C'   )  ; 16 } 17 18  /** The method for finding the solution to move n disks  19  from fromTower to toTower with auxTower */  

---

[Page 646]

 20   public static void    moveDisks(   int   n,   char   fromTower,  21    char   toTower,   char   auxTower)  { 22   if   (n ==   1   )  // Stopping condition  23 System.out.println(   "Move disk "   + n +   " from "   + 24 fromTower +   " to "   + toTower); 25   else   { 26  moveDisks(n -   1   , fromTower, auxTower, toTower)  ; 27 System.out.println(   "Move disk "   + n +   " from "   + 28 fromTower +   " to "   + toTower); 29  moveDisks(n -   1   , auxTower, toTower, fromTower)  ; 30 } 31 } 32 } 

This problem is inherently recursive. Using recursion makes it possible to find a natural, simple solution. It would be difficult to solve the problem without using recursion.

Consider tracing the program for n = 3 . The successive recursive calls are shown in Figure 19.6. As you can see, writing the program is easier than tracing the recursive calls. The system uses stacks to trace the calls behind the scenes. To some extent, recursion provides a level of abstraction that hides iterations and other details from the user.

Figure 19.6. Invoking moveDisks(3, 'A', 'B', 'C') spawns calls to moveDisks recursively.