Tower of Hanoi in Python: Recursive Algorithm and Move Count

Quick answer: The classic three-peg Tower of Hanoi solution moves n – 1 disks to an auxiliary peg, moves the largest disk to the target, and moves the n – 1 disks onto the target. It takes 2**n – 1 moves, so printed demonstrations should stay small and larger runs should avoid unnecessary output.

Tower of Hanoi in Python is a classic recursion exercise. The puzzle has three rods and n disks. The goal is to move all disks from the source rod to the target rod while never placing a larger disk on top of a smaller disk.

Tower of Hanoi rules

• Move only one disk at a time.
• Only the top disk on a rod can be moved.
• A larger disk cannot be placed on top of a smaller disk.
• Use the auxiliary rod to temporarily hold disks while moving the stack.

Recursive idea

To move n disks from A to C using B:

• Move n - 1 disks from A to B.
• Move the largest disk from A to C.
• Move n - 1 disks from B to C.

That is why recursion fits the puzzle: each step is the same problem with one fewer disk.

Tower of Hanoi Python code

This version returns a list of moves instead of printing inside the recursive function. Returning data makes the function easier to test and reuse.

def tower_of_hanoi(n, source, auxiliary, target):
    if n <= 0:
        return []
    moves = []
    moves.extend(tower_of_hanoi(n - 1, source, target, auxiliary))
    moves.append((source, target))
    moves.extend(tower_of_hanoi(n - 1, auxiliary, source, target))
    return moves

for move_number, (source, target) in enumerate(tower_of_hanoi(3, "A", "B", "C"), start=1):
    print(f"Move {move_number}: {source} -> {target}")

Output for three disks:

Move 1: A -> C
Move 2: A -> B
Move 3: C -> B
Move 4: A -> C
Move 5: B -> A
Move 6: B -> C
Move 7: A -> C

Print moves directly

For a small script or classroom example, printing directly from the recursive function is also fine.

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

solve_hanoi(2, "A", "B", "C")

This prints the three moves needed to solve a two-disk puzzle.

Minimum number of moves

The minimum number of moves for n disks is 2 ** n - 1. Three disks require 7 moves, four disks require 15, and five disks require 31.

def minimum_moves(disks):
    if disks < 0:
        raise ValueError("disk count cannot be negative")
    return 2 ** disks - 1

for disks in range(1, 6):
    print(disks, minimum_moves(disks))

Output:

1 1
2 3
3 7
4 15
5 31

Validate the move count

You can test the recursive function by checking the number of returned moves.

def tower_of_hanoi(n, source, auxiliary, target):
    if n < 0:
        raise ValueError("disk count cannot be negative")
    if n == 0:
        return []
    return (
        tower_of_hanoi(n - 1, source, target, auxiliary)
        + [(source, target)]
        + tower_of_hanoi(n - 1, auxiliary, source, target)
    )

moves = tower_of_hanoi(4, "A", "B", "C")
print(len(moves))

For four disks, this prints 15, matching 2 ** 4 - 1.

Time and space complexity

The recursive solution makes 2 ** n - 1 moves, so its time complexity is O(2^n). The recursion depth is n, so the call stack uses O(n) space, not counting the list of moves. If you store every move in a list, the stored output also uses O(2^n) space.

Can Tower of Hanoi be solved without recursion?

Yes. There are iterative solutions, including binary-pattern approaches, but recursion is usually the clearest way to learn the puzzle. For very large n, recursion depth and the exponential number of moves become practical limits. If you hit recursion depth errors in other recursive code, see our guide to RecursionError in Python.

Common mistakes

• Using the same rod order in every recursive call: the source, auxiliary, and target roles change in each step.
• Forgetting the base case: stop when n == 0 or n <= 0.
• Thinking the algorithm is linear: each extra disk roughly doubles the number of moves.
• Mutating global state unnecessarily: returning a move list keeps the function easier to test.
• Expecting large inputs to finish quickly: 30 disks require more than one billion moves.

Related Python guides

• Fix RecursionError in Python
• Insertion sort in Python
• Strand sort in Python
• Bitonic sort in Python
• Rock paper scissors in Python
• Python timer

Reference

• OEIS A000225: 2^n - 1 and Tower of Hanoi move counts

Conclusion

Tower of Hanoi is a clean example of recursion because the solution for n disks depends on solving the same puzzle for n - 1 disks. In Python, write a clear base case, move the smaller stack to the auxiliary rod, move the largest disk, then move the smaller stack to the target rod.

State The Rules First

Move exactly one top disk at a time, move only a top disk from a peg, and never place a larger disk on a smaller one. Writing the rules as an invariant makes both the recursive algorithm and its tests easier to verify.

Follow The Recursive Decomposition

To move n disks from source to target, move n - 1 from source to auxiliary, move the largest disk once, then move n - 1 from auxiliary to target. The base case moves one disk directly. The recursive structure mirrors the proof of correctness.

Validate The Move Count

The recurrence T(n) = 2T(n - 1) + 1 gives T(n) = 2**n - 1. Count generated moves and assert the formula for small n. This catches missing recursive branches and accidental extra output even when the final peg arrangement looks plausible.

Control Output And Recursion

Printing every move grows exponentially and can dominate runtime. Keep a non-printing solver for tests, use a move callback when a caller needs selected output, and remember that Python's recursion limit makes an explicit stack more appropriate for larger educational experiments.

Test The Invariants

Simulate the pegs, reject illegal moves, assert the final arrangement, and test n=0, n=1, and several small positive values. A test that checks only the move count can miss a sequence that has the right length but violates the disk rule.

The Python functions tutorial covers recursive function definitions. Related guidance includes algorithm tests and controlled diagnostic output.

For related algorithm design, compare recursion limits, algorithm tests, and timing experiments when scaling a recursive demonstration.

Frequently Asked Questions

What is the minimum number of Tower of Hanoi moves?

For n disks and three pegs, the minimum is 2**n - 1 moves.

Why is Tower of Hanoi recursive?

The solution for n disks contains two solutions for n-1 disks around one move of the largest disk, creating a direct recursive structure.

How many disks can the Python recursive solution handle?

The algorithm grows exponentially in moves and is also limited by recursion depth, so use small n for printed demonstrations and an explicit stack for larger experiments.

What rule must every move follow?

Move only one top disk at a time and never place a larger disk on top of a smaller disk.