Tower of Hanoi
mediumTime: O(2^n)Space: O(n)
Recognize the pattern
move n disks between pegscan't place larger on smallerclassic recursion
Brute force idea
Not applicable — recursion IS the solution. Minimum moves = 2^n - 1.
Better approach
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.
Key invariant
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.
Watch out for
Trying iterative without understanding the recursion — while iterative solutions exist, the recursive decomposition is the natural insight.