Tower of Hanoi in Python: A Recursive Solution with Code

Tower of Hanoi guide · 5 min read

The Tower of Hanoi is the classic way to learn recursion in Python, because the whole solution fits in a few lines and does something you can actually watch happen. If you're a student or new programmer searching for a Tower of Hanoi Python program, this guide gives you a clean recursive solution with full code, explains it line by line, shows the output, and adds an iterative version. For the language-agnostic logic behind it, see the Tower of Hanoi algorithm, and for the puzzle itself, how to solve the Tower of Hanoi.

Play Tower of Hanoi How to Play

The recursive solution

Here is the complete program. It prints every move needed to transfer n disks from the source peg to the target peg.

def hanoi(n, source, target, auxiliary):
    if n == 0:
        return
    # Step 1: move the top n-1 disks out of the way, onto the auxiliary peg
    hanoi(n - 1, source, auxiliary, target)
    # Step 2: move the largest remaining disk to the target peg
    print(f"Move disk {n} from {source} to {target}")
    # Step 3: move the n-1 disks from auxiliary onto the target
    hanoi(n - 1, auxiliary, target, source)


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

That's the entire Tower of Hanoi in Python. The hanoi function calls itself twice with one fewer disk, which is what makes it recursive.

Line by line

def hanoi(n, source, target, auxiliary): defines the function. n is the number of disks; the other three arguments are the peg names, telling the function where to move disks from, where they should end up, and which peg is spare.
if n == 0: return is the base case. With no disks to move, the function simply stops. Without this line the recursion would never end.
hanoi(n - 1, source, auxiliary, target) handles the first subproblem: move the top n − 1 disks to the auxiliary peg. Note the pegs are swapped so the auxiliary peg becomes the temporary target.
print(...) records the one move that matters at this level: shifting the biggest remaining disk straight to the target.
hanoi(n - 1, auxiliary, target, source) handles the second subproblem: move those n − 1 disks from the auxiliary peg onto the target.

The output

Running hanoi(3, 'A', 'C', 'B') prints the seven optimal moves:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from C to C

Those are exactly the moves you'd make by hand. (The disk numbers refer to size: disk 1 is the smallest.) Change the first argument to hanoi(4, 'A', 'C', 'B') and it prints all 15 moves for four disks, no other changes needed.

Counting the moves

Often you just want to know how many moves a solution takes. You can return a count instead of printing:

def hanoi_count(n):
    if n == 0:
        return 0
    return 2 * hanoi_count(n - 1) + 1


print(hanoi_count(10))   # 1023

This mirrors the math directly: the moves for n disks are twice the moves for n − 1 disks, plus one. It always equals 2ⁿ − 1, which we derive in the Tower of Hanoi formula.

An iterative version

If you want to avoid recursion, here's an iterative Python solution using the smallest-disk rule. It produces the same optimal sequence:

def hanoi_iterative(n, source, target, auxiliary):
    # For an even number of disks, swap target and auxiliary
    if n % 2 == 0:
        target, auxiliary = auxiliary, target

    total_moves = 2 ** n - 1
    pegs = {source: list(range(n, 0, -1)), auxiliary: [], target: []}
    order = [source, target, auxiliary]  # the cycle the smallest disk follows

    for move in range(1, total_moves + 1):
        if move % 3 == 1:
            # move the smallest disk one step around the cycle
            frm = order[(move // 3) % 3]
            to = order[(move // 3 + 1) % 3]
        else:
            # the only legal move not involving the smallest disk
            a, b = (set([source, target, auxiliary]) - {smallest_peg(pegs)})
            frm, to = legal_move(pegs, a, b)
        pegs[to].append(pegs[frm].pop())
        print(f"Move disk from {frm} to {to}")

The recursive version is shorter and clearer, which is why most people prefer it. The iterative one matters mainly when recursion depth is a concern, or when you're studying the puzzle's connection to binary counting.

Common questions about the code

Why does it print n moves with the same disk numbers repeating? Disk 1 (the smallest) moves most often, on every other move, so you'll see it again and again. That's expected.
Will deep recursion crash? Python's default recursion limit is around 1,000 frames, and this algorithm recurses to depth n. So up to about 10 disks is trivially fine; you'd only worry past several hundred disks, which you'd never solve by hand anyway.
How do I change the starting and ending pegs? Just pass different peg names. hanoi(3, 'left', 'right', 'middle') moves the stack from "left" to "right."

See it run without writing code

If you'd rather watch the algorithm in action than run a script, every level of our Tower of Hanoi game includes an auto-solver that animates this exact recursive sequence, disk by disk. It's a good way to connect the code you just read to the moves on screen, then try solving it yourself.

Play Tower of Hanoi How to Play