Skip to content
Tutorials Center
My learning

Topics

Lesson 70 of 225 ยท Recursion and Backtracking

Tower of Hanoi

Solve the Tower of Hanoi in Python with recursion, prove it needs 2^n - 1 moves, count moves, and learn the iterative solution and the ruler-sequence pattern.

The Tower of Hanoi is the puzzle that made many programmers fall in love with recursion. You have three pegs and a stack of disks of different sizes on the first peg, the biggest at the bottom. You must move the whole stack to another peg, obeying two rules: you may move only one disk at a time, and you may never put a bigger disk on top of a smaller one.

Try it by hand with five disks and it feels impossible. Try it with a recursive idea and the solution is four lines of code. The puzzle is small enough to hold in your head, yet it shows the core of recursive thinking: trust the smaller problem, and solve only the one step that is left.

The recursive idea

Call the pegs A (source), C (target) and B (spare). To move n disks from A to C:

  1. Move the top n - 1 disks from A to B, using C as the spare.
  2. Move the biggest disk from A to C. This is one move.
  3. Move the n - 1 disks from B to C, using A as the spare.

Step 1 and step 3 are the same problem with one disk fewer, only with different roles for the pegs. The biggest disk never blocks anything, because every other disk is smaller and can sit on top of it. And the base case is trivial: with zero disks there is nothing to do.

flowchart TD
    S["hanoi(n, source, target, spare)"] --> Q{"n == 0?"}
    Q -- yes --> R["return (nothing to move)"]
    Q -- no --> A["hanoi(n-1, source, spare, target)"]
    A --> M["move disk n: source to target"]
    M --> B["hanoi(n-1, spare, target, source)"]

The three steps of the recursive solution. The two recursive calls swap the roles of the pegs.

Python Move three disks from A to C

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the output from top to bottom. Disk 1 (the smallest) moves every second step, and disk 3, the biggest, moves exactly once, in the middle.

Why it takes 2^n - 1 moves

Let T(n) be the number of moves for n disks. The recursion gives a recurrence directly:

TEXT
T(0) = 0
T(n) = T(n-1) + 1 + T(n-1) = 2*T(n-1) + 1

Unroll it: T(1) = 1, T(2) = 3, T(3) = 7, T(4) = 15. Each value is one less than a power of two, so T(n) = 2^n - 1. A short proof by induction: T(0) = 2^0 - 1 = 0, and if T(n-1) = 2^(n-1) - 1, then T(n) = 2*(2^(n-1) - 1) + 1 = 2^n - 1.

It is also the best possible. To move the biggest disk, all n - 1 smaller disks must first sit together on the spare peg, which costs at least T(n-1) moves. After the biggest disk moves they must travel again, another T(n-1). So no solution can beat 2*T(n-1) + 1.

The time is therefore O(2^n): adding one disk doubles the work. With 64 disks and one move per second you would need about 585 billion years, which is the origin of the legend about monks and the end of the world. The space is only O(n), the depth of the recursion, because the pegs are never stored in full.

Python Count moves without listing them

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Peg states with a stack per peg

Printing moves is nice, but a real program usually wants to perform them. Represent each peg as a Python list used as a stack (the end of the list is the top). Then every move is a pop from one list and an append to another, and you can check the rule "never a bigger disk on a smaller one" at each step.

Python Execute the moves on real pegs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The program would raise an error if the algorithm ever broke the rule. It never does, which is a nice sanity check you can reuse for your own variants.

An iterative solution

Recursion is not the only way. There is a simple loop that produces the very same sequence of moves. Number the disks 1 (smallest) to n (biggest). Then repeat until the puzzle is solved:

  1. Move the smallest disk one peg in a fixed direction. For an odd number of disks the cycle is A -> C -> B -> A; for an even number it is A -> B -> C -> A.
  2. Make the only legal move that does not involve the smallest disk. (There is always exactly one, unless the puzzle is finished.)

Stop after 2^n - 1 moves. This works because the smallest disk moves every other step, and the other move is forced.

Python Iterative Hanoi with a fixed direction for disk 1

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The ruler pattern

Look at which disk moves at each step of the 3-disk solution: 1, 2, 1, 3, 1, 2, 1. This is the ruler sequence. The disk moved at step k (counting from 1) is the number of trailing zero bits of k, plus one. Step 4 is binary 100, which has two trailing zeros, so disk 3 moves. Odd steps always move disk 1.

That connects the puzzle to bit manipulation: you can find the disk for any step in O(1), without simulating the earlier steps. It is also why the position of the puzzle is a Gray code: between consecutive states exactly one disk changes peg.

Python Which disk moves at step k?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Variations worth knowing

  • Four pegs (the Reve's puzzle): more room means fewer moves. The Frame-Stewart algorithm is the best known strategy, but nobody has proven that it is optimal for all n.
  • Cyclic Hanoi: you may only move disks clockwise around the three pegs. The recursion splits into two mutually recursive functions.
  • Hanoi with a goal state: given any legal arrangement, find the shortest path to another one. The ruler structure still lets you solve it in O(n).

The recursion in this lesson also shows up when you study divide and conquer and the recurrences in recursion patterns.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many moves does the optimal solution need for 5 disks?

    T(n) = 2^n - 1, so T(5) = 32 - 1 = 31.
  2. 2. In the recursive solution, what is the role of the spare peg in the first recursive call?

    Step 1 is hanoi(n-1, source, spare, target): the smaller disks go to the spare peg so the biggest disk is free to move to the target.
  3. 3. What is the extra space used by the recursive algorithm, not counting the output?

    The recursion is n levels deep, so the call stack uses O(n) space. The 2^n - 1 moves are produced one by one.
  4. 4. Which recurrence describes the number of moves?

    Two recursive calls on n-1 disks plus one move of the biggest disk.

Summary

  • Move n disks by moving n-1 out of the way, moving the biggest disk once, and moving the n-1 back on top.
  • The minimum number of moves is 2^n - 1, so the running time is O(2^n) and the stack depth is O(n).
  • The recurrence T(n) = 2T(n-1) + 1 is solved by unrolling or by induction, and the bound is optimal.
  • An iterative version alternates between moving the smallest disk in a fixed direction and the one other legal move.
  • The disk moved at step k follows the ruler sequence: the position of the lowest set bit of k.

Next: Josephus Problem