Tower of Hanoi
mediumTime: O(2^n)Space: O(n)
Signals to notice
move n disks between pegscan't place larger on smallerclassic recursion
Brute force first
Not applicable — recursion IS the solution. Minimum moves = 2^n - 1.
The key insight
Move n-1 disks to auxiliary. Move largest to target. Move n-1 from auxiliary to target. T(n) = 2T(n-1) + 1 = 2^n - 1.
What must stay true
To expose the bottom disk, all n-1 above must be elsewhere. This creates two identical subproblems of size n-1 plus one direct move.
Easy way to go wrong
Trying iterative without understanding the recursion — while iterative solutions exist, the recursive decomposition is the natural insight.