Towers of Hanoi

Assume you can already move n−1 disks and the algorithm writes itself. Believing the smaller case is exactly what makes recursion work, and exactly what makes it hard to learn.