Programming and Problem Solving with Java

13.2 M o r e Examples with Simple Variables | 645

The last circle (circle 1) can now be moved into its final place, and we are finished:

This algorithm certainly sounds simple; surely, there must be more to it! But this solution
really is all there is.
Let’s write a recursive method that implements this algorithm. We can’t actually move
discs, of course, but we can print out a message to do so. Notice that the beginning peg, the
ending peg, and the auxiliary peg keep changing during the algorithm. To make the algorithm
easier to follow, we call the pegs beginPeg,endPeg, and auxPeg. These three pegs, along with the
number of circles on the beginning peg, are the parameters of the method.
We have the recursive (general) case, but what about a base case? How do we know
when to stop the recursive process? The clue lies in the expression “Getncircles moved.”
If we don’t have any circles to move, we don’t have anything to do. We are finished with
that stage. Therefore, when the number of circles equals 0, we do nothing (that is, we sim-
ply return).

public static voiddoTowers(
int circleCount, // Number of circles to move
int beginPeg, // Peg containing circles to move
int auxPeg, // Peg holding circles temporarily
int endPeg ) // Peg receiving circles being moved
// Moves are written on file outFile
{
if (circleCount > 0)
{
// Move n – 1 circles from beginning peg to auxiliary peg

Get n Circles Moved from Peg 1 to Peg 3

Get n – 1 circles moved from peg 1 to peg 2

Move nth circle from peg 1 to peg 3

Get n – 1 circles moved from peg 2 to peg 3

1

12 3 123

4 4

3

2

1

3

2

2 1

12 3 123

4 4

3

2

1

3