The Tower of Hanoi comes up almost every time people learn “recursion” in programming. Solving it by hand takes hundreds of moves, yet as a program it takes just a few lines. Let’s look at how that works, step by step. The poles are left, middle and right, and the disks are numbered 1, 2, 3… from smallest to largest.
What Is Recursion?
Recursion means using the same procedure on a smaller problem inside the procedure that solves a problem. As the problem shrinks, you eventually reach a problem whose answer is obvious right away (for example, with 0 disks you do nothing), and that is where it stops.
Thinking About the Tower of Hanoi with Recursion
Think about moving a tower of n disks from the left to the right.
- Move the top n − 1 disks from the left to the middle.
- Move the largest disk, n, from the left to the right.
- Move the n − 1 disks in the middle to the right.
Steps 1 and 3 are the problem “move a tower of n − 1 disks”, which has the same shape as the original problem. Only the poles it moves from and to are different. So if you write one procedure, “move n disks from one pole to another, using the remaining pole”, it can call itself inside.
Pseudocode
procedure hanoi(n, from, to, spare):
if n is 0, do nothing and finish
hanoi(n − 1, from, spare, to) … move the top n−1 disks aside
move disk n from "from" to "to"
hanoi(n − 1, spare, to, from) … bring the n−1 disks back
hanoi(3, left, right, middle) gives the moves for 3 disks from the left to the right This alone produces the fewest-moves solution for any number of disks. Working Python and C code is in Solving the Tower of Hanoi in Python and C.
How the Calls Branch
When you write out how hanoi is called for 3 disks, you get a tree shape like this. The deeper the indentation, the more deeply nested the call.
hanoi(3, left→right)
├─ hanoi(2, left→middle)
│ ├─ hanoi(1, left→right) … 1 to the right
│ ├─ 2 to the middle
│ └─ hanoi(1, right→middle) … 1 to the middle
├─ 3 to the right
└─ hanoi(2, middle→right)
├─ hanoi(1, middle→left) … 1 to the left
├─ 2 to the right
└─ hanoi(1, left→right) … 1 to the right The sequence of “moves”, read from the top down, is exactly the answer of 7 moves. One call produces two calls inside it, so every time you add one disk, the work roughly doubles.
Cost
| What to measure | For n disks |
|---|---|
| Number of moves | 2ⁿ − 1 |
| Number of calls to hanoi (counting calls with 0 disks) | 2ⁿ⁺¹ − 1 |
| Depth of the calls (how much to remember at once) | n + 1 levels |
Why the number of moves is 2ⁿ − 1 is proved in the minimum-moves formula. The time grows exponentially with the number of disks (O(2ⁿ)), while the amount to remember grows only in proportion to the number of disks (O(n)). Since there are 2ⁿ − 1 moves themselves, however cleverly you do it, writing out the whole solution takes at least this much time.
Solving Without Recursion
You can also solve it with just a loop, without recursion. It is exactly the procedure for solving by hand that is introduced in the article on how to solve it.
procedure hanoi_loop(n):
decide the direction of disk 1 (if n is odd: left→right→middle; if even: left→middle→right)
repeat for move = 1, 2, 3, … , 2ⁿ − 1:
if move is odd, move disk 1 to the next pole in the chosen direction
if move is even, compare the top disks of the two poles without disk 1,
and move the smaller one onto the larger one (or onto an empty pole) You do not need to remember calls the way recursion does, so it uses very little memory.
Finding Any Move Directly with Binary
There is also a way to find what to do on any move directly, without following the moves before it. Number the poles 0, 1 and 2. For move m (counting from 1):
- The disk to move is disk number (the number of trailing 0s when m is written in binary) + 1.
- The pole to move from is (m AND (m − 1)) divided by 3, taking the remainder.
- The pole to move to is ((m OR (m − 1)) + 1) divided by 3, taking the remainder.
AND and OR are the calculations that work digit by digit on binary numbers, “and” and “or”. For example, for m = 4 (100 in binary), there are 2 trailing 0s, so the disk is number 3. The pole to move from is (4 AND 3) = 0, so pole 0. The pole to move to comes from ((4 OR 3) + 1) = 8, and 8 divided by 3 leaves a remainder of 2, so pole 2.
The moves this formula produces move the tower from pole 0 to pole 2 if the number of disks is odd, and from pole 0 to pole 1 if it is even. If you want to move an even number of disks to pole 2, swap poles 1 and 2 when you read it. The connection between the number of moves and binary is explained in more detail in the article on patterns.
