Discrete Mathematics for Computer Science

550 CHAPTER 9 Recurrence Relations

In Figure 9.2, examples of legal and illegal moves are shown. The algorithm for solv-

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