Home / Python / Example programs / Functions and recursion

Python program: Tower of Hanoi

Move a stack of discs between three pegs, one disc at a time, never putting a larger disc on a smaller one.

The code

def hanoi(n, source, target, spare, moves):
    if n == 0:
        return
    hanoi(n - 1, source, spare, target, moves)   # move the smaller stack out of the way
    moves.append((n, source, target))            # move the biggest disc
    hanoi(n - 1, spare, target, source, moves)   # put the smaller stack back on top

moves = []
hanoi(3, "A", "C", "B", moves)
for disc, a, b in moves:
    print(f"move disc {disc} from {a} to {b}")
print(len(moves), "moves (always 2**n - 1)")

Output

move disc 1 from A to C
move disc 2 from A to B
move disc 1 from C to B
move disc 3 from A to C
move disc 1 from B to A
move disc 2 from B to C
move disc 1 from A to C
7 moves (always 2**n - 1)

How it works

The recursive idea: to move n discs, move n−1 out of the way, move the biggest, then move the n−1 back on top. The base case is zero discs.

Python features used

Learn the ideas behind it in the free lesson More Functions.