Mathwords logoMathwords

Tower of Hanoi — Definition, Formula & Examples

The Tower of Hanoi is a mathematical puzzle where you move a stack of differently sized disks from one peg to another, one disk at a time, without ever placing a larger disk on top of a smaller one.

The Tower of Hanoi is a problem defined on three pegs and nn ordered disks of distinct sizes. The objective is to transfer all nn disks from a source peg to a target peg, moving exactly one disk per step, subject to the constraint that no disk may rest on a smaller disk. The minimum number of moves required is 2n−12^n - 1.

Key Formula

T(n)=2n−1T(n) = 2^n - 1
Where:
  • T(n)T(n) = Minimum number of moves to solve the puzzle with n disks
  • nn = Number of disks

How It Works

The puzzle is solved recursively. To move nn disks from peg A to peg C, first move the top n−1n-1 disks from A to the spare peg B. Then move the largest disk directly from A to C. Finally, move the n−1n-1 disks from B to C. Each subproblem has the same structure, which is why this puzzle is a classic example of recursion. The base case is n=1n = 1: simply move the single disk to the target peg.

Worked Example

Problem: Find the minimum number of moves needed to solve the Tower of Hanoi with 4 disks.
Apply the formula: Substitute n=4n = 4 into the minimum-moves formula.
T(4)=24−1T(4) = 2^4 - 1
Compute: Calculate the power of 2 and subtract 1.
T(4)=16−1=15T(4) = 16 - 1 = 15
Answer: The minimum number of moves to solve the Tower of Hanoi with 4 disks is 15.

Visualization

Why It Matters

The Tower of Hanoi is one of the first problems students encounter when learning recursion in computer science courses. Its exponential growth—doubling with each added disk—provides a concrete, tangible example of O(2n)O(2^n) time complexity. It also appears in algorithm design textbooks as a gateway to divide-and-conquer strategies.

Common Mistakes

Mistake: Confusing the recursive formula T(n)=2T(n−1)+1T(n) = 2T(n-1) + 1 with the closed-form T(n)=2n−1T(n) = 2^n - 1 and miscounting moves.
Correction: Both are correct representations. The recursive relation describes the strategy (move n−1n-1 disks, move the largest, move n−1n-1 again), while 2n−12^n - 1 is its closed-form solution. Use whichever fits the context, but verify they agree.