What is the Tower of Hanoi?
The Tower of Hanoi is a classical mathematical puzzle consisting of three pegs and $N$ disks of different sizes. The objective of the puzzle is to move the entire stack of disks from the Source Peg to the Destination Peg using an Auxiliary Peg, obeying three simple rules:
- Only one disk can be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty peg.
- No larger disk may be placed on top of a smaller disk.
The puzzle is resolved using a Divide and Conquer recursive strategy:
- Base Case ($N=1$): Directly move the single disk from Source to Destination.
- Recursive Case ($N > 1$):
- Move the top $N-1$ disks from Source to Auxiliary using Destination.
- Move the remaining largest disk from Source to Destination.
- Move the $N-1$ disks from Auxiliary to Destination using Source.
The Recurrence Relation
To find the number of moves $T(N)$ required to solve the puzzle for $N$ disks, we can express the operations as a mathematical recurrence relation:
T(N) = 2T(N - 1) + 1, with base case T(1) = 1
Let's solve this recurrence relation using substitution:
- T(N) = 2T(N-1) + 1
- T(N) = 2[2T(N-2) + 1] + 1 = 2²T(N-2) + 2 + 1
- T(N) = 2³T(N-3) + 2² + 2¹ + 2⁰
- ...
- T(N) = 2^(N-1)T(1) + 2^(N-2) + ... + 2¹ + 2⁰
- T(N) = 2^(N-1) + 2^(N-2) + ... + 2¹ + 2⁰
This is a geometric progression with a sum of:
T(N) = 2^N - 1
For example, if we have $N = 3$ disks, the total number of moves will be $2^3 - 1 = 7$ moves. Adding just one more disk doubles the size of the recursion tree, requiring $2^4 - 1 = 15$ moves!
Complexity Analysis
Since solving the puzzle for $N$ disks requires resolving two sub-problems of size $N-1$ and executing 1 constant time disk move, the recursion tree doubles in width at every level. The total operations equal $2^N - 1$, which grows exponentially.
The call stack size is determined by the height of the recursion tree. Since we recurse down to $N-1$ before executing moves, the maximum number of frames on the call stack at any point during execution is $N$. Therefore, the auxiliary space complexity is linear, $O(N)$.