Recursion - Java Software Solutions: Foundations of Program Design - page 597

Original Configuration Fourth Move

First Move Fifth Move

Second Move Sixth Move

Third Move Seventh (last) Move

FIGURE 12.6 A solution to the three-disk Towers of Hanoi puzzle

This strategy lends itself nicely to a recursive solution. The step to move the N −1
disks out of the way is the same problem all over again: moving a stack of disks.
For this subtask, though, there is one less disk, and our destination peg is what
we were originally calling the extra peg. An analogous situation occurs after we've
moved the largest disk and we have to move the original N −1 disks again.
The base case for this problem occurs when we want to move a “stack” that
consists of only one disk. That step can be accomplished directly and without
recursion.
The program in Listing 12.3 creates a TowersOfHanoi object and invokes its
solve method. The output is a step-by-step list of instructions that describe how
the disks should be moved to solve the puzzle. This example uses four disks,
which is specified by a parameter to the TowersOfHanoi constructor.
The TowersOfHanoi class shown in Listing 12.4 uses the solve method to make
an initial call to moveTower , the recursive method. The initial call indicates that
all of the disks should be moved from peg 1 to peg 3, using peg 2 as the extra
position.
The moveTower method first considers the base case (a “stack” of one disk).
When that occurs, it calls the moveOneDisk method that prints a single line

VideoNote

Exploring the Towers of
Hanoi.