The Tower of Hanoi

Three pegs stand in a row, and on the first is a tower of discs, each smaller than the one below it. The task is to move the whole tower to the third peg. Only one disc may move at a time, always the top disc of a peg, and a disc may never be put on a smaller one.

With one disc it is one move. With two, put the small disc on the middle peg, move the large one across, and put the small one back on top: three moves. With three it already takes some thought. Recursion makes it easy.

1#include <stdio.h>2 3#ifndef DISCS4#define DISCS 35#endif6 7static int moves = 0;8 9void hanoi(int n, char from, char to, char via)10{11    if (n == 0)12        return;13    hanoi(n - 1, from, via, to);14    printf("disc %d: %c -> %c\n", n, from, to);15    moves++;16    hanoi(n - 1, via, to, from);17}18 19int main(void)20{21    hanoi(DISCS, 'A', 'C', 'B');22    printf("%d moves\n", moves);23    return 0;24}

The plan

Think about the largest disc, disc n. It has to get from A to C, and it can only move when nothing is on top of it and nothing is on C that is smaller than it. So at that moment the other n − 1 discs must all be on B. That gives the whole plan:

1. Move the top n − 1 discs from A to B, using C as the spare peg.
2. Move disc n from A to C.
3. Move the n − 1 discs from B to C, using A as the spare.

Steps 1 and 3 are the same problem with one disc fewer and the pegs renamed. The base case is a tower of no discs, which needs no moves at all; one disc is then just step 2. You can also take one disc as the base case, as many books do; the moves are the same.

The code and its cost

The program

void hanoi(int n, char from, char to, char via)
{
    if (n == 0)
        return;
    hanoi(n - 1, from, via, to);
    printf("disc %d: %c -> %c\n", n, from, to);
    moves++;
    hanoi(n - 1, via, to, from);
}

The three pegs are three char parameters, and the plan renames them for each smaller tower: the first call swaps to and via, the second swaps from and via. Nobody plans the seven moves ahead. Each call knows only its own three steps, and the right moves come out.

main calls hanoi(DISCS, 'A', 'C', 'B'), with DISCS set to 3 unless the compiler is told otherwise. It prints the seven moves and 7 moves.

Counting the moves

Write M(n) for the moves the plan makes for n discs. It makes M(n − 1) moves, then one, then M(n − 1) again:

So M(1) = 1, M(2) = 3, M(3) = 7, M(4) = 15, M(5) = 31 and M(6) = 63: each is one less than a power of two, and

(Check: 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1.) Drag the slider to count them. Each extra disc doubles the work, which is exponential growth, like fib’s calls in Tree recursion (4.3). Solving equations like this one is the subject of 21.2.

No plan does better

Could some cleverer order use fewer moves? No. Disc n has to move at least once. Before its first move, the other n − 1 discs must all be stacked on the third peg, which is a whole tower of n − 1 moved: at least M(n − 1) moves. After its last move, they must all come back on top of it: at least M(n − 1) more. So any plan needs at least 2M(n − 1) + 1 moves, and the recursive plan makes exactly that many.

Calls and the stack

Each call that moves a disc makes two more calls, so there are 2ⁿ⁺¹ − 1 calls in all, counting the calls with no discs: 15 for 3 discs, of which 7 move a disc. The stack is never deeper than one card per disc plus one for the zero-disc call at the bottom: n + 1 cards, 4 for 3 discs. The work grows exponentially, but the stack only grows by one card per disc.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic hanoi.c -o hanoi
./hanoi
gcc -std=c11 -Wall -Wextra -pedantic -DDISCS=4 hanoi.c -o hanoi4
./hanoi4

The second prints 15 moves.

Worked example

Who moves how often. In the 7 moves for 3 discs, disc 1 moves 4 times, disc 2 twice and disc 3 once. In general disc k moves 2ⁿ⁻ᵏ times. The smallest disc makes every other move: moves 1, 3, 5 and 7. Watch disc 1 in the clip; drag to 6 discs and it still moves every other time.

The first move. With 3 discs, disc 1 goes first to C. With 4 discs it goes first to B. For an odd number of discs the smallest disc starts towards the target peg, for an even number towards the spare.

64 discs. 2⁶⁴ − 1 = 18,446,744,073,709,551,615 moves. At one move a second, that is about 5.8 × 10¹¹ years.

Before you read on, three to try:

1. How many moves for 5 discs? (31.)
2. How many cards are on the stack at the most for 4 discs? (5: one per disc, plus the call with none.)
3. Which disc makes move 8 of the 15 for 4 discs? (Disc 4, the largest: it moves once, right in the middle.)

Where it’s used

Learning to think recursively. The Tower of Hanoi is the standard first example of a problem that is hard to plan move by move and easy to solve by handing smaller copies of it to the same function.

Gray codes. Write down which discs have moved an odd number of times after each move, one bit per disc, and successive states differ in exactly one bit. Codes with that property, Gray codes, are used in position encoders, where a shaft’s angle is read from a pattern of stripes: changing only one bit at a time means a reading taken between two positions is never wildly wrong.

Recurrences. M(n) = 2M(n − 1) + 1 is a first example of a recurrence, an equation that gives a cost in terms of smaller costs. They describe the running time of most recursive algorithms (21.2).

Reference card

Platform: C11, gcc on x86-64 Linux.