RECURSION - Java Programming: From Problem Analysis to Program Design - page 886

Move disk 1 from needle 1 to needle 3

Move 1

1 2

1

Move disk 2 from needle 1 to needle 2

Move 2

2

1 3 2 1

Move disk 1 from needle 3 to needle 2

Move 3

1 3 2 1 3

Move disk 3 fro m needl e 1 to needle 3

Move 4

1

1

3 2 3

Move disk 1 from needle 2 to needle 1

Move 5

1

2 3 1 2 3

Move disk 2 fro m needl e 2 to needle 3

Move 6

2 1 2 3 1

Move disk 1 from needle 1 to needle 3

Move 7

1

2 1

FIGURE 13-7 Solution to Tower of Hanoi problem with three disks

Let's now generalize this problem to the case of 64 disks. To begin, the first needle
contains all 64 disks. Disk number 64 cannot be moved from needle 1 to needle 3
unless the top 63 disks are on the second needle. So first we move the top 63 disks
from needle 1 to needle 2, and then we move disk number 64 from needle 1 to
needle 3. Now the top 63 disks are all on needle 2. To move disk number 63 from
needle 2 to needle 3, we first move the top 62 disks from needle 2 to needle 1, and
then we move disk number 63 from needle 2 to needle 3. To move the remaining
62 disks, we use a similar procedure. This discussion translates into the following