Taking the pseudo code from
CMU's Computer Science site:
Code:
FUNCTION MoveTower(disk, source, dest, spare):
IF disk == 0, THEN:
move disk from source to dest
ELSE:
MoveTower(disk - 1, source, spare, dest) // Step 1
move disk from source to dest // Step 2
MoveTower(disk - 1, spare, dest, source) // Step 3
END IF
Assume there are 6 discs labeled from 0-5 with 5 being the largest and 0 being the smallest. Also assume that there are 3 pegs labeled A, B and C. The initial state of the puzzle looks like this:
A: [5][4][3][2][1][0]
B:
C:
Say you call
MoveTower(5, A, B, C). When your program reaches this line...
Code:
MoveTower(disk - 1, source, spare, dest) // Step 1
...what happens is that your program will put the call to
MoveTower(5, A, B, C) "on hold", and attempt to do
MoveTower(4, A, C, B) first.
In
MoveTower(4, A, C, B), it will encounter...
Code:
MoveTower(disk - 1, source, spare, dest) // Step 1
...again, after which it puts
MoveTower(4, A, C, B) on hold while it calls
MoveTower(3, A, B, C). Each function keeps calling itself until it hits
MoveTower(0, A, C, B), at which point it'll move the disc 0 (the smallest one), from A to C, as per this clause...
Code:
IF disc == 0, THEN:
move disc from source to dest
...resulting in this state of the puzzle:
A: [5][4][3][2][1]
B:
C: [0]
Now, all the
MoveTower(...) calls that have been piling up can start resolving one by one in reverse order. The function that was most recently paused was
MoveTower(1, A, B, C), which had reached this line:
Code:
move disk from source to dest
The program will then move disc 1 to B, resulting in:
A: [5][4][3][2]
B: [1]
C: [0]
The next line in the function is...
Code:
MoveTower(disk - 1, spare, dest, source) // Step 3 above
...which translates to
MoveTower(0, C, B, A), because it was called during the call to
MoveTower(1, A, B, C). Going back to the first disc, the program will encounter...
Code:
IF disc == 0, THEN:
move disc from source to dest
...again, resulting in this state.
A: [5][4][3][2]
B: [1][0]
C:
The program has just completed the Tower of Hanoi problem for two discs. The next function on the stack is
MoveTower(2, A, C, B), and it will do...
Code:
move disk from source to dest
... leading to:
A: [5][4][3]
B: [1][0]
C: [2]
And so on and so forth. I don't think you really need to understand why this specific algorithm works, or how it was deduced. What's important is being able to understand that a function can call itself and how it can be used to solve certain programming problems, particularly those that can be broken down into small yet similar problems.