While solving the CSES Tower of Hanoi problem, I started looking for patterns in the recursive solution instead of directly implementing it.

I ended up deriving an iterative approach based on two observations:

• The sequence of which disk moves follows a recursive pattern.
• Every disk follows a fixed cyclic path between the three pegs, with odd- and even-numbered disks rotating in opposite directions.

Using these observations, we can generate every move without explicitly performing the classical recursive algorithm.

This is not an optimization — the solution still requires O(2ⁿ) time because we must output 2ⁿ - 1 moves. My implementation also uses O(2ⁿ) memory because it stores the generated disk order, while the classical recursive approach can be implemented with only O(n) extra memory.

The interesting part is the derivation and the patterns hidden behind the recursion.

Full explanation and code:

Deriving an Iterative Tower of Hanoi Algorithm from Movement Patterns

The write-up covers:

• How the sequence of moving disks can be generated.
• The cyclic movement pattern of each disk.
• How the source and destination pegs can be calculated directly.
• A further observation using __builtin_ctzll that removes the need to generate the disk sequence entirely.

I found it interesting that the recursive solution can be viewed as a consequence of simple movement patterns. Would love to hear if anyone has other interesting characterizations of the Tower of Hanoi!