The Tower of Hanoi Problem
551
It is instructive to follow the steps of the procedure for an initial configuration involving three disks. The steps in this recursive procedure are shown in Figure 9.3 using
a tree. The actual computation order can be found by an inorder traversal of the tree (see
Section 6.12.3).
TRANS(3,,1,23,32)
TRANS(1, 2, 1,3)
T
RANS(1, 1, 3, 2)
Figure 9.3 Recursion tree for Tower of Hanoi algorithm.
INPUT: Three pegs, named 1, 2, and 3, and N disks stacked by decreasing radius
on peg 1, with the biggest disk at the bottom
OUTPUT: The N disks are stacked by decreasing radius on peg 3, with the biggest
disk at the bottom
TRANS(N, 1, 3, 2) /* Move the top N disks from peg I to peg 3 */
TRANS(k, PegFrom, PegTo, PegUsing) !* The recursive procedure */
1. if (k = 1) then
move the top disk from PegFrom to PegTo
else
TRANS (k-i, PegFrom, PegUsing, PegTo)
move the top disk on PegFrom to PegTo
TRANS (k-i, PegUsing, PegTo, PegFrom)