RECURSION - Introduction to Java Programming - page 752

0 2

n - 1 disks n - 1 disks

.

.

A B

Original position

C A B

Step 2: Move disk n from A to B

C

1

3

n - 1 disks

n - 1 disks

.

.

A B
Step 1: Move the first n - 1 disks from
A to C recursively

C A B

Step 3: Move n - 1 disks from
C to B recursively

C

F IGURE 20.7

The Towers of Hanoi problem can be decomposed into three subproblems.

The following method moves n disks from the fromTower to the toTower with the assis-
tance of the auxTower :

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

The algorithm for the method can be described as:

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 20.8 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.

L ISTING 20.8 TowersOfHanoi.java
1 import java.util.Scanner;
2
3 public class TowersOfHanoi {
4 /** Main method */
5 public static void main(String[] args) {
6 // Create a Scanner
7 Scanner input = new Scanner(System.in);
8 System.out.print( "Enter number of disks: " );
9

int n = input.nextInt();

10
11 // Find the solution recursively
12 System.out.println( "The moves are:" );
13 moveDisks(n, 'A' , 'B' , 'C' ) ;

14 }
15