# How do I show that an iterative solution to Tower of Hanoi performs the same exact steps as a recursive solution? [duplicate]

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

1. move (n-1) disks from start to auxiliary.
2. move the largest disk from start to destination.
3. 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