The puzzle

The Tower of Hanoi consists of three pegs and a set of discs of decreasing size stacked on the leftmost peg. The goal is to move the entire stack to another peg following these rules:

Move only one disc at a time.
A disc may only be placed on top of a larger disc or on an empty peg.

Start:           Goal:
Peg A  B  C     Peg A  B  C
 [1]            |    |  [1]
 [2]            |    |  [2]
 [3]            |    |  [3]

The math

The minimum number of moves required to solve an n-disc Tower of Hanoi is 2ⁿ − 1.

Discs (n)	Minimum moves (2ⁿ − 1)
1	1
2	3
3	7
4	15
5	31
10	1,023
20	1,048,575
64	18,446,744,073,709,551,615 (~584 billion years at 1 move/sec)

The recursive solution

The elegant recursive algorithm: to move n discs from peg A to peg C using peg B as auxiliary:

Move n−1 discs from A to B.
Move disc n from A to C.
Move n−1 discs from B to C.

This recursion produces exactly 2ⁿ − 1 moves and is the foundation for understanding recursion in computer science.

The iterative solution

The Tower of Hanoi can also be solved iteratively (without recursion) using just two rules:

On odd moves: move the smallest disc one peg to the right (cyclically: A->B->C->A).
On even moves: make the only legal move that does not involve the smallest disc.

Repeating these two steps alternately solves the puzzle in 2ⁿ − 1 moves. This also corresponds to counting in binary: each disc maps to a bit position, and a disc moves when its corresponding bit changes in the binary count from 0 to 2ⁿ − 1.

Why this problem matters in computer science

The Tower of Hanoi is a canonical teaching example for several reasons:

Recursion: the three-line recursive solution is one of the clearest demonstrations that a complex problem can be solved by defining it in terms of smaller instances of itself.
Binary counting: the sequence of moves corresponds exactly to incrementing a binary number; peg A = bit 0, peg B = bit 1, peg C = bit 2. This surprising connection between a physical puzzle and number representation is a favorite teaching moment.
Exponential complexity: the 2ⁿ − 1 move count demonstrates concretely why exponential-time algorithms quickly become impractical: 64 discs requires 18,446,744,073,709,551,615 moves.

Variations

4-peg (Reve's puzzle): adding a fourth peg reduces the minimum number of moves significantly. The Frame-Stewart conjecture proposes an optimal algorithm, but it has not been proven for all values of n - it remains an open problem in computer science.
Restricted Hanoi: allow moves only between adjacent pegs (A↔B, B↔C but not A↔C directly). The minimum move count increases to 3ⁿ − 1.
Bi-color Hanoi: discs have two colors and must be sorted by color as well as size.