There is a nice recursive solution to the Tower of Hanoi problem.
1 1
2 ---> 2
_3___.___._ _.___.___3_
i k j i k j
Imagine there is a function \(F(N, i, j)\) that can properly move a tower of height \(N\) (that is, disk \(1\)on top of \(2\), on top of … \(N\)) from position \(i\) to \(j\), using the “free” position \(k\). The function \(F\) operates on the full “state” of the pins and outputs a new “state”.
Note that the position \(k\) doesn’t have to be truly free — since it can only have disks of size more than \(N\) — it’s effectively free. This is because we’re assuming that the “state” is always correct (the disks are placed according to the rules).
Then, implementation of \(F(N+1,i,j)\) is:
Recursion terminates at \(F(1, i, j)\), which is trivial to implement — the disk of size \(1\) (the smallest) can always be moved anywhere.
So the sequence of calls for the picture above becomes:
Call stack:
State:
[1 2 3] [ ] [ ]
[2 3] [ ] [1]
[3] [2] [1]
[3] [1 2] [ ]
[ ] [1 2] [3]
[1] [2] [3]
[1] [ ] [2 3]
[ ] [ ] [1 2 3]
In this sequence, only some steps do the actual moves: \(F(1,\_,\_)\) and “move from _ to _”. The former can always be performed (because it’s the disk of size \(1\)). But it’s not obvious why the latter can always be performed.
Intuitively: