Tower of Hanoi Explained

To move n discs from one peg to another, using a third peg as the spare, you do three things. Move the top n minus one discs from the source to the spare peg. Move the single largest disc from the source to the target peg. Move the n minus one discs from the spare peg onto the target peg, on top of the largest one.

def hanoi(count, source, target, spare, moves=None):
    if moves is None:
        moves = []
    if count == 0:
        return moves
    hanoi(count - 1, source, spare, target, moves)
    moves.append((source, target))
    hanoi(count - 1, spare, target, source, moves)
    return moves


for move in hanoi(3, "A", "C", "B"):
    print(move)

The output is three moves: A to B, A to C and B to C. That is the classic seven-move solution for three discs, printed as the three top-level moves with the recursive steps flattened into the list.

The mechanism is that the top n minus one discs have to be out of the way before the largest disc can move, and they must then be stacked back on top of it. Each of those two transfers is itself a Tower of Hanoi problem with one fewer disc, which is why the function calls itself twice with the peg roles permuted. The base case of zero discs does nothing, which terminates the recursion.

The trade-off to name is the stack depth. The recursion nests n levels deep, so the space complexity is O of n, and the time is dominated by the number of moves, which is exponential. For thirty discs that is over a billion moves, so the practical version of this problem asks for the count rather than the moves, or asks for the moves in a compressed or grouped form. The three-peg structure is also what makes it a good recursion example: it is one of the simplest problems where the recursive decomposition is genuinely easier to see than the iterative version.

The minimum number of moves for n discs is two to the power n minus one. You can compute it with the formula, or by the same recursion that produces the moves, since the count satisfies the same recurrence as the solution itself.

def hanoi_moves(count):
    return 2 ** count - 1


def hanoi(count, source, target, spare):
    if count == 0:
        return
    hanoi(count - 1, source, spare, target)
    print(source, "->", target)
    hanoi(count - 1, spare, target, source)


for count in (1, 3, 10):
    print(count, hanoi_moves(count))

The outputs are 1, 1 then 3, 7 then 10, 1023. One disc needs a single move, three discs need seven and ten discs need a thousand and twenty-three.

The mechanism is the recurrence. Moving n discs requires moving n minus one discs twice, plus one move for the largest disc, so the count satisfies M of n equals two times M of n minus one plus one, with M of zero equal to zero. Solving that gives two to the power n minus one. The reason the number explodes is that each extra disc doubles the work rather than adding to it, which is the signature of an exponential algorithm.

The trade-off to name is that this is optimal in the sense that no legal solution can use fewer moves, because the n minus one smaller discs must be moved off the largest one and then back on, and each of those transfers is itself a problem of the same size. The puzzle with four pegs, where the count is much smaller for large n, is the standard illustration that the structure of the problem determines the complexity and not the algorithm alone. For thirty discs with three pegs, the count is over a billion, so no program finishes it, which is exactly why the formula is the useful part.