This question already has an answer here:
So given the typical recursive solution to the Tower of Hanoi problem wherein you reduce the n-disk tower to two instances of an (n-1)-disk tower i.e
- move (n-1) disks from start to auxiliary.
- move the largest disk from start to destination.
- move (n-1) disks from auxiliary to destination.
how do you then show that an iterative algorithm (shown below) performs the same exact steps? Intuitively you'd be using induction on $n$, but as to how that is done I'm not sure.
The iterative algorithm is as follows:
If $n$ is even, swap pegs $1$ and $2$. At the $i$th step, make the only legal move that avoids peg $i$ mod $3$. If there is no legal move, then all disks are on peg $i$ mod $3$, and the puzzle is solved