Editing Tower of Hanoi (section)

==== Non-recursive solution ====
{{More citations needed section|date=January 2024}}
The list of moves for a tower being carried from one peg onto another one, as produced by the recursive algorithm, has many regularities. When counting the moves starting from 1, the ordinal of the disk to be moved during move ''m'' is the number of times ''m'' can be divided by 2. Hence every odd move involves the smallest disk. It can also be observed that the smallest disk traverses the pegs ''f'', ''t'', ''r'', ''f'', ''t'', ''r'', etc. for odd height of the tower and traverses the pegs ''f'', ''r'', ''t'', ''f'', ''r'', ''t'', etc. for even height of the tower. This provides the following algorithm, which is easier, carried out by hand, than the recursive algorithm.

In alternate moves:
* Move the smallest disk to the peg it has not recently come from.
* Move another disk legally (there will be only one possibility).
For the very first move, the smallest disk goes to peg ''t'' if ''h'' is odd and to peg ''r'' if ''h'' is even.

Also observe that:
* Disks whose ordinals have even parity move in the same sense as the smallest disk.
* Disks whose ordinals have odd parity move in opposite sense.
* If ''h'' is even, the remaining third peg during successive moves is ''t'', ''r'', ''f'', ''t'', ''r'', ''f'', etc.
* If ''h'' is odd, the remaining third peg during successive moves is ''r'', ''t'', ''f'', ''r'', ''t'', ''f'', etc.

With this knowledge, a set of disks in the middle of an optimal solution can be recovered with no more state information than the positions of each disk:
* Call the moves detailed above a disk's "natural" move.
* Examine the smallest top disk that is not disk 0, and note what its only (legal) move would be: if there is no such disk, then we are either at the first or last move.
* If that move is the disk's "natural" move, then the disk has not been moved since the last disk 0 move, and that move should be taken.
* If that move is not the disk's "natural" move, then move disk 0.