0
$\begingroup$

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

$\endgroup$

marked as duplicate by David Richerby, Hendrik Jan, Evil, Apass.Jack, Discrete lizard Jan 18 at 16:22

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.