The Tower of Hanoi Algorithm: Recursive and Iterative Solutions Explained

Tower of Hanoi guide · 5 min read

The Tower of Hanoi is the textbook example of a recursive algorithm, which is why it shows up in nearly every introduction to computer science. The recursive solution is just three lines of logic, yet it perfectly solves the puzzle for any number of disks. This guide explains the Tower of Hanoi algorithm in plain language: the recursive version with pseudocode, the iterative alternative, the time complexity, and why both always produce the optimal 2ⁿ − 1 moves. If you want the hands-on version first, start with how to solve the Tower of Hanoi.

Play Tower of Hanoi How to Play

The problem, stated precisely

You have three pegs (call them source, auxiliary, and target) and n disks of distinct sizes stacked on the source peg, largest at the bottom. You must move all n disks to the target peg, moving one disk at a time, never placing a larger disk on a smaller one. The algorithm's job is to output the sequence of moves that does this.

The recursive algorithm

The recursive solution rests on a single insight: to move n disks from the source to the target, you first need the top n − 1 disks out of the way on the auxiliary peg. That reduces the problem to a smaller version of itself.

In words, the algorithm to move n disks from source to target using auxiliary is:

Move the top n − 1 disks from source to auxiliary (using target as the spare).
Move disk n (the largest) from source to target.
Move the n − 1 disks from auxiliary to target (using source as the spare).

The base case stops the recursion: moving zero disks does nothing.

Pseudocode

function hanoi(n, source, target, auxiliary):
    if n == 0:
        return                         # base case: nothing to move
    hanoi(n - 1, source, auxiliary, target)   # step 1
    move disk n from source to target          # step 2
    hanoi(n - 1, auxiliary, target, source)   # step 3

Notice how steps 1 and 3 call the same function with one fewer disk and the pegs swapped around. That self-reference is the entire algorithm. Each call breaks the puzzle into a slightly smaller puzzle until it hits n == 0 and unwinds.

Tracing it for 3 disks

Walking through hanoi(3, A, C, B) produces exactly the seven optimal moves:

A → C
A → B
C → B
A → C
B → A
B → C
A → C

These are the same moves you'd make by hand, which is the point: the algorithm is just the recursive pattern written down formally. You can see the same sequence built up by hand in our 3, 4 and 5 disk solutions.

The iterative algorithm

Recursion is the most elegant solution, but the Tower of Hanoi can also be solved with a simple loop, no function calls required. The iterative algorithm uses a fixed rule about the smallest disk:

Calculate the total number of moves, 2ⁿ − 1.
Decide the smallest disk's direction. If n is even, the smallest disk cycles source → auxiliary → target → source. If n is odd, it cycles source → target → auxiliary → source.
Then repeat until solved:
- On odd-numbered moves, move the smallest disk one step in its cycle direction.
- On even-numbered moves, make the only legal move that does not involve the smallest disk (there is always exactly one).

This produces the identical optimal sequence as the recursive version. It's handy when you want to avoid recursion (for example, on systems with limited stack depth) and it's the basis of the by-hand shortcut shown in how to solve the Tower of Hanoi.

Time and space complexity

Both algorithms make the minimum possible number of moves, 2ⁿ − 1, so the time complexity is O(2ⁿ), exponential in the number of disks. That's not a flaw in the algorithm; it's a property of the puzzle itself, since the puzzle genuinely requires that many moves. There's a full derivation in the Tower of Hanoi formula.

The recursive version's space complexity is O(n) because of the call stack: at its deepest, n nested calls are open at once. The iterative version uses O(1) extra space beyond the move output, which is its main practical advantage.

Why the recursive version is so loved in teaching

The Tower of Hanoi is the standard first lesson in recursion for a reason. It shows, in a way you can watch on screen, the three things every recursive solution needs:

A base case that stops the recursion (n == 0).
A smaller subproblem that looks exactly like the original (move n − 1 disks).
A combination step that uses the subproblems to finish the job (move the big disk, then move the smaller stack back).

Seeing those pieces in such a clean, visual puzzle makes the abstract idea of recursion concrete. More on that teaching value in what the Tower of Hanoi teaches.

See it in code

If you want a runnable version, our Tower of Hanoi in Python guide turns this exact pseudocode into a working program with output. And if you'd rather just watch the algorithm play out, every difficulty on our Tower of Hanoi game includes an auto-solver that animates the optimal sequence move by move.

Play Tower of Hanoi How to Play