Discrete Mathematics for Computer Science

The Tower of Hanoi Problem 551

It is instructive to follow the steps of the procedure for an initial configuration in-
volving 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)