Tower of Hanoi Algorithm

The Tower of Hanoi is the classic first example of recursion: a three-line algorithm that solves a tower of any size in the fewest possible moves.

The recursive algorithm

To move n disks from a source peg to a target peg, using the third peg as a spare:

1. Move the top n − 1 disks from the source to the spare peg.
2. Move the largest disk from the source to the target.
3. Move the n − 1 disks from the spare peg onto the target.

Steps 1 and 3 are the same problem with one disk fewer, so the function calls itself. The base case is a single disk, which simply moves. Every call makes the tower smaller, so the recursion always reaches the base case and stops.

Watch the recursion

Each line on the left is one call or one move, indented under the call that made it. Step through and the board follows.

Code in Python, Java and C++

The same algorithm in three languages. Each prints the 7 moves for 3 disks; change the 3 to try other sizes.

def hanoi(n, source, target, spare):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, spare, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, spare, target, source)

hanoi(3, "A", "C", "B")

public class Hanoi {
    static void hanoi(int n, char source, char target, char spare) {
        if (n == 1) {
            System.out.println("Move disk 1 from " + source + " to " + target);
            return;
        }
        hanoi(n - 1, source, spare, target);
        System.out.println("Move disk " + n + " from " + source + " to " + target);
        hanoi(n - 1, spare, target, source);
    }

    public static void main(String[] args) {
        hanoi(3, 'A', 'C', 'B');
    }
}

#include <iostream>

void hanoi(int n, char source, char target, char spare) {
    if (n == 1) {
        std::cout << "Move disk 1 from " << source << " to " << target << "\n";
        return;
    }
    hanoi(n - 1, source, spare, target);
    std::cout << "Move disk " << n << " from " << source << " to " << target << "\n";
    hanoi(n - 1, spare, target, source);
}

int main() {
    hanoi(3, 'A', 'C', 'B');
}

Time and space complexity

The function makes two calls on n − 1 disks plus one move, so the number of moves is T(n) = 2T(n − 1) + 1, which works out to 2ⁿ − 1. That is also the fewest moves possible.

• Time: O(2ⁿ). Each extra disk doubles the work: 10 disks take 1,023 moves, 20 disks over a million.
• Space: O(n). Only one chain of calls is open at a time, at most n deep.

Iterative solution, without recursion

The same moves can be made with a plain loop. On odd moves the smallest disk steps one peg along a fixed cycle (A → C → B for an odd number of disks, A → B → C for an even number). On even moves there is only one legal move that does not touch the smallest disk.

def hanoi_iterative(n):
    pegs = {"A": list(range(n, 0, -1)), "B": [], "C": []}
    # Disk 1 cycles A -> C -> B for an odd n, A -> B -> C for an even n.
    order = ["A", "C", "B"] if n % 2 else ["A", "B", "C"]
    for move in range(1, 2 ** n):
        if move % 2:  # odd moves: the smallest disk steps along its cycle
            i = next(k for k in range(3) if pegs[order[k]] and pegs[order[k]][-1] == 1)
            a, b = order[i], order[(i + 1) % 3]
        else:  # even moves: the only legal move that leaves disk 1 alone
            x, y = [p for p in "ABC" if not (pegs[p] and pegs[p][-1] == 1)]
            a, b = (x, y) if pegs[x] and (not pegs[y] or pegs[x][-1] < pegs[y][-1]) else (y, x)
        pegs[b].append(pegs[a].pop())
        print(f"Move disk {pegs[b][-1]} from {a} to {b}")

hanoi_iterative(3)

Copy the Python code