How does the recursive solution to the Tower of Hanoi work, and what does it do in each step?
You move the whole tower to the target peg by first moving all but the bottom disk to the spare peg, then moving the bottom disk to the target, and then moving the tower that is on the spare peg onto the target.
def hanoi(count, source, target, spare, moves=None):
if moves is None:
moves = []
if count == 0:
return moves
hanoi(count - 1, source, spare, target, moves)
moves.append((source, target))
hanoi(count - 1, spare, target, source, moves)
return moves
So what does it do in each step? Here is the whole thing for three disks, where the pegs are called A, B and C.
the move what moves from to
--------- --------------- ----- -----
1 the small disk A B
2 the middle disk A C
3 the small disk B C
4 the big disk A B
5 the small disk C A
6 the middle disk C B
7 the small disk A B
So the three steps in the code are the three lines in the body. The first call moves the smaller disks out of the way, from the source to the spare peg. The line in the middle moves the one big disk from the source to the target. And the last call moves the tower that is now on the spare peg onto the target.
And the reason the first call has to happen is a rule of the puzzle. You can never put a big disk on a smaller disk. So before the big disk can move to the target peg, the target peg has to be empty, and that means all the smaller disks have to be somewhere else. And they cannot stay on the source peg either, because the big disk is under them there. So the only place for them is the spare peg.
And the stopping condition is when there are no disks left. Then there is nothing to do and the function returns.
And this is a good example of a recursive problem because the sub-problem is the same as the whole problem with one fewer disk. It is also the classic example for teaching recursion, because the idea is hard to say in words and easy to see in the code.
So the rule to remember is this. Move the small ones aside, move the big one, and then move the small ones back on top.
The last question in this topic asks how many moves it takes.