550
CHAPTER 9 Recurrence Relations
In Figure 9.2, examples of legal and illegal moves are shown. The algorithm for solving the problem for n disks that is presented here involves solving a similar problem for
n - 1 disks twice. An implementation of this algorithm involves recursive calls to the
procedure.
Peg I
Peg 2
Peg 3
Peg I
Peg 2
Peg 3
(a) Legal Move
I C-L
_
I
_
'
Peg I
Peg 2
Peg 3
Peg I
Peg 2
Peg 3
(b) Illegal Move
Figure 9.2 Examples of legal and illegal moves, a. Legal move. b. Illegal move.