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