wishful thinking
strategy
- decide what would make the problem simpler
- pretend you can solve the simpler version
- work out how to use this solution to solve the original problem
- work out how to solve the smallest problem
here
- what makes it simpler: fewer disks
- to solve for k disks, pretend we can solve for any number of disks less than k
- to solve original problem
move the k-1 disks to the extra peg
move the remaining, biggest disk to the destination peg
move the disks on the extra peg to the destination
- smallest problem is no disks: do nothing