Tower of Hanoi (Recursive & Non-recursive)

YASH PAL,

Algorithm – Tower of Hanoi (recursive)

TOWER(N,BEG,AUX,END)
This procedure gives a recursive solution to the Towers of Hanoi problem for N disks.

1. If N = 1, then:
         (a) Write: BEG -> END.
         (b) Return.
    [End of If structure.]

2. [Move N – 1 disks from BEG to AUX.]
    Call TOWER(N -1, BEG, END, AUX).

3. Write: BEG -> END.

4. [Move N – 1 disks from AUX to END.]
    Call TOWER(N – 1, AUX, BEG, END).

 

Algorithm – Tower of Hanoi (Non-recursive)

TOWER(N, BEG, AUX, END)
This is a non-recursive solution to the Tower of Hanoi problem for N disks. which is obtained by translating the recursive solution. Stacks STN STSRC. STTARG, STAUX, and STADD will correspond to the variable N, BEG, AUX, END, and ADD.

0. Set TOP: = NULL [Initally all stacks are empty]
1.  If N = 1, then:
        (a) Write BEG -> END.
        (b) Go to Step 5
    [End of If structure]
2. [Translation of “Call TOWER(N-1,BEG,END,AUX)”]
         [Push current values and new return address onto stacks.]
                 (i) Set TOP:=TOP+1
                 (ii) Set STN[TOP]: = N, STBEG[TOP]: = BEG STEND[TOP]:
                      = END, STAUX[TOP]: = AUX, STADD[TOP]: = 3
         [Reset Parameters.]
                 Set N: = N – 1, BEG: = BEG, AUX: = END, END: = AUX
         (C) Go to Step 1
3. Write: BEG -> END.
4. [Translation of “Call TOWER(N – 1, AUX, BEG, END)”]
         (a) [Push current values and new return address onto stacks.]
                (i) Set TOP: = TOP + 1
               (ii) Set STN[TOP]: = N, STBEG[TOP]: = BEG,
                    STEND[TOP]: = END, STAUX[TOP]: = AUX,
                    STADD[TOP]: = 5
         (b) [Reset Parameters.]
               Set N: = N – 1, BEG: = AUX, AUX: = BEG,
               END = END
         Go to Step 1
5. [Translation of “Return”]
         (a) If TOP: = NULL, then Return.
         (b) [Restore top values on stacks.]
               (i) Set N: = STN[TOP], BEG: = STBEG[TOP],
                    END: = STEND[TOP], AUX: = STAUX[TOP],
                    ADD: = STADD[TOP]
              (ii) Set TOP: = TOP – 1
(c) Go to Step ADD

algorithms data structures