Module 4 · Interactive topic

Tower of Hanoi

Recursion, the call stack and the call tree

Move a tower of disks from peg A to peg C, using peg B as a helper. The trick is recursion: to move n disks, first move n − 1 out of the way, move the biggest disk, then move the n − 1 back on top. Each call waits on the call stack, and all the calls together form a tree. Try N = 1, 2 and 3.

  • Rule 1one disk at a time
  • Rule 2never a big disk on a small one
  • Moves2ⁿ − 1 for n disks
  • Stackevery waiting call sits on it
Tower of Hanoi Ready
The pegs
Call stack (top first)
Call tree (trace) — leaves are the base cases; read left to right: the moves
  • Not called yet
  • Running
  • Moving a disk
  • Finished

Ready

Comparisons 0 Shifts 0
Ready

Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode

How it works

Every operation, in plain steps

These are exactly the steps the visualizer animates.

The recursive idea

To move n disks from A to C: (1) move the top n − 1 disks from A to B, using C as the helper; (2) move the biggest disk from A to C; (3) move the n − 1 disks from B to C, using A as the helper. Steps 1 and 3 are the SAME problem with one disk fewer, so the function calls itself. With one disk there is nothing smaller to solve — that is the base case. A call that is waiting for its inner calls sits on the call stack.

void hanoi(int n, char from, char to, char via) {
    if (n == 1) {                                          // base case
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    hanoi(n - 1, from, via, to);                           // 1. n-1 disks out of the way
    printf("Move disk %d from %c to %c\n", n, from, to);   // 2. the biggest disk
    hanoi(n - 1, via, to, from);                           // 3. n-1 disks back on top
}

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

The three parts

  1. Move n − 1 disks from A to B (out of the way).
  2. Move disk n from A to C.
  3. Move the n − 1 disks from B to C (back on top).
  4. Parts 1 and 3 are smaller copies of the same problem.

The base case

  1. With one disk there is nothing smaller to solve.
  2. Just move disk 1.
  3. No more calls: the recursion stops here.
  4. Without it the function would call itself forever.

N = 2 (3 moves)

  1. hanoi(2) calls hanoi(1): disk 1 goes A → B.
  2. Then disk 2 goes A → C.
  3. Then hanoi(1) again: disk 1 goes B → C.
  4. The call tree has 3 boxes.

N = 3 (7 moves)

  1. hanoi(3) calls hanoi(2): two disks A → B (3 moves).
  2. Disk 3 goes A → C (move 4).
  3. hanoi(2) again: two disks B → C (3 moves).
  4. The call tree has 7 boxes.

The call stack

  1. A call is pushed when it starts.
  2. It waits there while its inner calls run.
  3. It is popped when it finishes.
  4. For n disks the stack is at most n calls deep.

The call tree (the trace)

  1. Every call is a box; its two inner calls are its children.
  2. The leaves are the base cases.
  3. Read the tree inorder (left, box, right): the moves, in order.
  4. Boxes = moves = 2ⁿ − 1.

Why 2ⁿ − 1 moves

  1. T(1) = 1 and T(n) = 2 × T(n − 1) + 1.
  2. Each extra disk doubles the work, plus one move.
  3. 1, 3, 7, 15, 31 … 1,023 moves for 10 disks.
  4. 64 disks would need about 1.8 × 10¹⁹ moves.
Algorithm

Pseudocode

Language-independent steps. The visualizer shows the same logic in C, Python and Java.

1 HANOI(n, from, to, via)
2 if n = 1 then
3 move disk 1 from → to // base case
4 return
5 HANOI(n − 1, from, via, to) // 1. get the smaller disks out of the way
6 move disk n from → to // 2. the biggest disk
7 HANOI(n − 1, via, to, from) // 3. put the smaller disks back on top
Complexity

How fast is each operation?

n = number of disks. The number of moves is exactly 2ⁿ − 1, and no solution can use fewer. The call stack holds at most n calls, so the extra memory is only O(n).

Operation Best Average Worst Speed
Moves (and calls) O(2ⁿ) O(2ⁿ) O(2ⁿ) Grows with n
Call stack depth O(n) O(n) O(n) Grows with n
One call (without its inner calls) O(1) O(1) O(1) Instant

How big do the numbers get?

Disks (N) Moves = 2ⁿ − 1 Calls Deepest call stack Tree levels
1 1 1 1 1
2 3 3 2 2
3 7 7 3 3
4 15 15 4 4
10 1,023 1,023 10 10

N = 3: the 7 moves (the call tree read inorder)

Move Disk From → To Made by the call
1 1 A → C hanoi(1, A, C, B)
2 2 A → B hanoi(2, A, B, C)
3 1 C → B hanoi(1, C, B, A)
4 3 A → C hanoi(3, A, C, B)
5 1 B → A hanoi(1, B, A, C)
6 2 B → C hanoi(2, B, C, A)
7 1 A → C hanoi(1, A, C, B)
Practice

Check your understanding

Answer each question — you will see the explanation straight away.

0 / 6 correct
Question 1

How many moves does the Tower of Hanoi need for 3 disks?

Question 2

The call tree for N = 3 has how many base cases (leaves)?

Question 3

For N = 3, how deep does the call stack get at most?

Question 4

Reading the call tree for N = 3 inorder (left, box, right) gives…

Question 5

One more disk makes the number of moves…

Question 6

What stops the recursion?

Assessment

Stacks quiz

Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.

Create a free account →
← Previous topic Expression Conversion Next topic → Queues