Tower of Hanoi
The Tower of Hanoi is a mathematical puzzle that demonstrates recursion elegantly. You have three rods and a number of disks of different sizes. The objective is to move the entire stack to another rod, obeying two rules: only one disk may be moved at a time, and no disk may be placed on top of a smaller disk.
Loading demo…
Algorithm explanation
The recursive solution: to move n disks from A to C using B — move n-1 disks from A to B, move the largest disk from A to C, then move n-1 disks from B to C. Base case: moving 1 disk is a single step.
Concepts used
- Recursion
- Stack
- Divide and Conquer
Complexity
Time:
O(2^n)Space:
O(n)Real-world usage
- Teaching recursion in computer science
- Backup rotation schemes (e.g. following the same recurrence)
- Analysis of recursive algorithms