Towers of Hanoi

Why it matters

The Towers of Hanoi is a puzzle with three pegs and a pile of disks. Trial and error gets slow as the number of disks grows, but the recursive solution is only a few lines long. It is a clear example of a rule you will use in many recursion problems: solve a smaller copy of the same problem, then use that answer to solve the bigger one.

The puzzle also shows how fast work can grow. Each extra disk doubles the number of moves. You will count the moves exactly, and you will see why printing every move stops being practical around 30 disks, where the output has over a billion lines.

The puzzle

There are three pegs, named A, B and C. A peg is a vertical rod that a disk can slide onto. The disks are flat rings of different sizes. Disk 1 is the smallest, and disk n is the largest. At the start, all n disks are on peg A, with the largest at the bottom and the smallest at the top.

The goal is to move every disk to peg C. There are three rules:

• You move one disk at a time.
• You may only move the top disk of a peg.
• You may never place a disk on top of a smaller disk.

Start with one disk. You move it from A to C, and the puzzle is done in one move.

Start with two disks. Disk 1 sits on top of disk 2, so disk 1 must move first, out of the way. It goes to B. Then disk 2 can move from A to C. Last, disk 1 moves from B onto C, on top of disk 2. The full list of moves is three lines:

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

Three disks take more work, and by hand it is easy to make a mistake. A recursive method gives the answer for any number of disks without you having to hold the whole plan in your head.

The idea: the largest disk moves once

Look at the largest disk, disk n. It has to move from A to C at some point. When it moves, three things are true:

• Disk n is alone on peg A, because it is the bottom disk and it is about to move.
• All the other n - 1 disks are on the spare peg, which is B, because they are smaller and sit on top of disk n.
• Peg C is empty, so disk n can land on it.

That gives a plan with three steps:

1. Move the top n - 1 disks from A to B. Peg C is the spare peg for this step.
2. Move disk n from A to C. This is one move.
3. Move the n - 1 disks from B to C. Peg A is the spare peg for this step.

Steps 1 and 3 are the same puzzle as the original, but with one fewer disk. So the function can call itself for those steps. The smallest version of the puzzle is zero disks. With zero disks there is nothing to move, so the function stops there. That stopping case is the base case.

Each call needs four things: how many disks to move, which peg they start on, which peg they must finish on, and which peg is the spare. The function takes four inputs: the number of disks, the starting peg (called from), the target peg (called to), and the spare peg (called spare). Each call relabels the pegs. In the first recursive call, the target is B, so B becomes to and C becomes spare. The names stay the same inside each call, but the pegs they stand for change.

Here is the whole solution. It prints each move as it happens.

Read the function from the top. The first if is the base case. The first recursive call moves the top disks out of the way. The cout line is step 2, the one move of the largest disk in this call. The last recursive call is step 3. The print sits between the two calls, so the moves come out in the order they must happen.

The program reads the number of disks from the input. Compile and run it with these commands:

g++ -std=c++20 -Wall -o show show.cpp
./show

The -std=c++20 flag selects the C++ 2020 standard, and -Wall turns on the common warnings. After you run ./show, type the number of disks and press Enter.

Worked example 1: one disk

Input: 1

The call is hanoi(1, 'A', 'C', 'B'). The number of disks is not zero, so the function goes on. The first recursive call is hanoi(0, 'A', 'B', 'C'). It does nothing. The print line runs and shows the one move. The last recursive call is hanoi(0, 'B', 'C', 'A'), which also does nothing.

Output:

Move disk 1 from A to C

Worked example 2: two disks

Input: 2

The call hanoi(2, 'A', 'C', 'B') first calls hanoi(1, 'A', 'B', 'C'). That call moves disk 1 from A to B. Back in the outer call, the print line moves disk 2 from A to C. Then the outer call makes its last recursive call, hanoi(1, 'B', 'C', 'A'), which moves disk 1 from B to C.

Output:

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

This is the same list that you worked out by hand in the puzzle section.

Worked example 3: three disks

Input: 3

Output:

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 A to C

The output has a pattern you can check against the plan. The first three lines move the two smaller disks from A to B. That is the two-disk solution from example 2, but with C as the spare peg, so its moves are different. The fourth line moves disk 3 from A to C, and disk 3 moves only once. The last three lines move the two smaller disks from B to C, with A as the spare. Again, that is the two-disk solution with different peg names.

Count the lines: 7. The next section explains why 7 is the right number for three disks.

Checking a move list against the rules

A printed list is only useful if every move follows the rules. The program below stores the pegs as three vectors. Each vector holds disk numbers, and its last item is the top disk. It applies the seven moves from example 3 in order, and it stops at the first move that breaks a rule.

Output for the correct list:

A:
B:
C: 3 2 1

Peg C lists its disks from bottom to top, so the bottom disk 3 is first. Pegs A and B are empty at the end, which is the goal of the puzzle.

Now change the second move to {2, 'A', 'C'}. Disk 2 would go to peg C while disk 1 is still on it. The checker stops at that move:

step 2: illegal, disk 2 cannot go on top of smaller disk 1

The program returns exit code 1 at that point, so a script can tell that the list failed. This is a useful habit when you write a solver. Test the output with a checker, not only with your eyes.

Counting the moves

A program that counts moves does not need to print them. It only needs to add one for each move. Here is the same recursion with a counter instead of a print. The function returns the number of moves for n disks.

The count for n disks is the count for n - 1 disks, times two, plus one. In a formula, with moves(0) equal to 0, that is moves(n) = 2 * moves(n - 1) + 1. Start from 0 and apply the rule:

• With 1 disk: 2 * 0 + 1 = 1
• With 2 disks: 2 * 1 + 1 = 3
• With 3 disks: 2 * 3 + 1 = 7
• With 4 disks: 2 * 7 + 1 = 15

Each result is one less than a power of 2. The pattern is 2^n - 1, where 2^n means 2 multiplied by itself n times. You can prove it with one step. If the count for n - 1 disks is 2^(n-1) - 1, then the count for n disks is 2 * (2^(n-1) - 1) + 1, which is 2^n - 2 + 1, or 2^n - 1.

Here is the output of the program above:

n=1  counted=1  2^n-1=1  equal=yes
n=2  counted=3  2^n-1=3  equal=yes
n=3  counted=7  2^n-1=7  equal=yes
n=4  counted=15  2^n-1=15  equal=yes
n=5  counted=31  2^n-1=31  equal=yes
n=6  counted=63  2^n-1=63  equal=yes
n=7  counted=127  2^n-1=127  equal=yes
n=8  counted=255  2^n-1=255  equal=yes
n=9  counted=511  2^n-1=511  equal=yes
n=10  counted=1023  2^n-1=1023  equal=yes
n=11  counted=2047  2^n-1=2047  equal=yes
n=12  counted=4095  2^n-1=4095  equal=yes
n=13  counted=8191  2^n-1=8191  equal=yes
n=14  counted=16383  2^n-1=16383  equal=yes
n=15  counted=32767  2^n-1=32767  equal=yes
n=16  counted=65535  2^n-1=65535  equal=yes
n=17  counted=131071  2^n-1=131071  equal=yes
n=18  counted=262143  2^n-1=262143  equal=yes
n=19  counted=524287  2^n-1=524287  equal=yes
n=20  counted=1048575  2^n-1=1048575  equal=yes
largest unsigned long long: 18446744073709551615

The counter type is unsigned long long. It is a whole-number type that uses 64 bits, which are binary digits, so it holds values up to 18446744073709551615. The program writes 1ULL, where the ULL suffix makes the 1 an unsigned long long. Then 1ULL << n shifts the bits of that 1 left by n places, which doubles it n times. So (1ULL << 3) is 8, and (1ULL << n) - 1 is the formula from above.

The shift only works for n up to 63. Shifting a 64-bit number by 64 places or more is not defined by the C++ standard, so the formula must stop before that.

The number of moves grows quickly. With 64 disks, the puzzle needs 2^64 - 1 moves, which is the largest value in the output above. At one move per second, that is about 584 billion years. That is why the puzzle is a good example of exponential growth: each new disk doubles the work.

Counting by running the recursion also takes about 2^n calls, so for large n it is slow too. For a count, use the formula directly.

Printing the moves for a small case

Printing is the expensive part. A program that prints every move writes 2^n - 1 lines. For 3 disks that is 7 lines, which is easy to check by eye. For 20 disks it would be 1,048,575 lines. Print the moves for small cases to check the logic, and use the formula for large ones.

Common mistakes

Forgetting the base case

If the function has no if (n == 0) check, it never stops. Here is a version with the base case removed:

#include <iostream>
 
unsigned long long hanoi_count(int n) {
    return 2 * hanoi_count(n - 1) + 1;
}
 
int main() {
    std::cout << hanoi_count(3) << "\n";
}

The compiler warns about it. The wording differs between compiler versions; this is g++ 15:

m_nobase.cpp: In function 'long long unsigned int hanoi_count(int)':
m_nobase.cpp:3:20: warning: infinite recursion detected [-Winfinite-recursion]
    3 | unsigned long long hanoi_count(int n) {
      |                    ^~~~~~~~~~~
m_nobase.cpp:4:27: note: recursive call
    4 |     return 2 * hanoi_count(n - 1) + 1;
      |                ~~~~~~~~~~~^~~~~~~

When the program runs, each call starts another call before it returns. The computer runs out of stack memory, which is the space used to track the calls that have not finished yet. The program is stopped with a segmentation fault, and the shell reports exit code 139. A segmentation fault means the program tried to use memory it is not allowed to use.

Passing the wrong number of arguments

Here is a program with a call that is missing one argument:

#include <iostream>
 
void hanoi(int n, char from, char to, char spare) {
    if (n == 0) {
        return;
    }
    hanoi(n - 1, from, spare, to);
    std::cout << "Move disk " << n << " from " << from << " to " << to << "\n";
    hanoi(n - 1, spare, to, from);
}
 
int main() {
    hanoi(3, 'A', 'C');
}

The compiler stops with an error:

m_missing.cpp: In function 'int main()':
m_missing.cpp:13:10: error: too few arguments to function 'void hanoi(int, char, char, char)'
   13 |     hanoi(3, 'A', 'C');
      |     ~~~~~^~~~~~~~~~~~~
m_missing.cpp:3:6: note: declared here
    3 | void hanoi(int n, char from, char to, char spare) {
      |      ^~~~~

The first line says what is wrong: too few arguments. The note line shows where the function is defined and what it expects. The fix is to pass all four values, for example hanoi(3, 'A', 'C', 'B').

Swapping the spare and the target

The two recursive calls must swap the target and the spare. If the first call uses the wrong peg order, the program still prints moves, but some of them break the rules. This version uses to where it should use spare:

#include <iostream>
 
void hanoi(int n, char from, char to, char spare) {
    if (n == 0) {
        return;
    }
    hanoi(n - 1, from, to, spare);
    std::cout << "Move disk " << n << " from " << from << " to " << to << "\n";
    hanoi(n - 1, spare, to, from);
}
 
int main() {
    hanoi(2, 'A', 'C', 'B');
}

Running it with two disks prints this:

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

The second line puts disk 2 on peg C while disk 1 is still there. The rules forbid that. The program does not check the rules, so the only way to catch the error is to compare the output with the plan.

Storing the count in an int

An int is a signed whole number, and on most systems it holds values up to 2147483647. That is 2^31 - 1. The count for 31 disks fits, but the count for 32 disks does not. Here is the counting function written with int:

#include <iostream>
 
int hanoi_count(int n) {
    if (n == 0) {
        return 0;
    }
    return 2 * hanoi_count(n - 1) + 1;
}
 
int main() {
    std::cout << hanoi_count(31) << "\n";
    std::cout << hanoi_count(32) << "\n";
}

Compile it with the undefined behaviour checker, which is part of g++:

g++ -std=c++20 -Wall -fsanitize=undefined -o m_overflow m_overflow.cpp

Output:

m_overflow.cpp:7:14: runtime error: signed integer overflow: 2147483647 * 2 cannot be represented in type 'int'
2147483647
-1

The checker prints the first line, which is the overflow report, before the program's own output. The count for 32 disks should be 4294967295, but the int version cannot hold it. In C++, signed integer overflow is undefined behaviour, which means the program may print anything. Use unsigned long long for move counts.

Practice

Exercise 1: The first moves for four disks

Without running any code, write the first four moves for 4 disks from A to C. Then check your answer with the program.

Show the answer

The first four moves are:

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

The first three moves are the two-disk solution from A to C, using B as the spare. Then disk 3 moves from A to B, because the top three disks have to be on B before the largest disk can move.

Exercise 2: Moves for 30 disks

How many moves does the puzzle need for 30 disks? Use the formula, not the recursion.

Show the answer

The answer is 2^30 - 1, which is 1073741823. The program below prints it:

Output:

1073741823

Exercise 3: Moves per disk

For 5 disks, how many times does each disk move? Predict the pattern before you write the program. Then write a program that counts the moves for each disk.

Show the answer

Disk 1 moves 16 times, disk 2 moves 8 times, disk 3 moves 4 times, disk 4 moves 2 times and disk 5 moves once. The pattern is that disk k moves 2^(n - k) times, where k is the disk number and n is the number of disks.

Output:

disk 1 moves 16
disk 2 moves 8
disk 3 moves 4
disk 4 moves 2
disk 5 moves 1

The vector has n + 1 entries so that moves_per_disk[n] is valid for disk n. Index 0 is not used.

Exercise 4: Numbered moves

Change the program so each line starts with the move number. Use it for 2 disks.

Show the answer

Add a counter. The counter goes up each time the program prints a move.

Output:

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

Exercise 5: The count without recursion

Write a function that returns the number of moves for n disks, with no recursion. Check it for n from 0 to 5.

Show the answer

The formula is (1ULL << n) - 1. For n equal to 0, the shift gives 1, and 1 - 1 is 0, which matches the zero moves for zero disks.

Output:

n=0 moves=0
n=1 moves=1
n=2 moves=3
n=3 moves=7
n=4 moves=15
n=5 moves=31

Summary

• The recursive plan moves the top n - 1 disks out of the way, moves the largest disk once, then moves the n - 1 disks back on top of it.
• The base case is zero disks, where the function does nothing.
• Each call names its pegs as from, to and spare, and the recursive calls swap the roles of the pegs.
• The number of moves follows moves(n) = 2 * moves(n - 1) + 1, which gives 2^n - 1.
• Use unsigned long long for move counts, and stop the shift formula before 64.
• Print the moves only for small numbers of disks, because the printed output doubles with each disk.