2n − 1 moves, and not one fewer.
Move every disk from A to C. One disk at a time, always from the top of a peg, and never onto a smaller disk. Play it yourself first, then watch the recursion do it.
Pick the peg to take a disk from.
Press Next to make the first call.
The largest disk is the only one that matters at each level. It can move exactly when every smaller disk is out of its way — stacked on the spare peg — and its target peg is empty. So the solution to n disks is three instructions: move the top n − 1 to the spare, move the largest across, move the n − 1 back on top of it.
Moving n − 1 disks is the same problem again, with the pegs playing different parts. In Watch the recursion, the labels under the pegs show which peg is from, which is to, and which is via for the frame on top of the stack. Watch them rotate as the recursion descends: that rotation is the only thing the code changes between calls.
Trust the call to move n − 1 disks. You only ever move one disk yourself.
| disks | moves | at one move a second |
|---|---|---|
| 3 | 7 | 7 seconds |
| 10 | 1,023 | 17 minutes |
| 20 | 1,048,575 | 12 days |
| 30 | 1,073,741,823 | 34 years |
| 64 | 18,446,744,073,709,551,615 | 585 billion years |
Adding one disk doubles the work and adds one move. The board above stops at 10 disks for that reason: 1,023 moves is already a long game.
The recurrence. Let T(n) be the moves the recursion makes for n disks. It moves n − 1 disks, then one disk, then n − 1 disks again, so T(n) = 2 T(n − 1) + 1, with T(1) = 1. That gives 1, 3, 7, 15, 31… Each value is one less than a power of two, and if T(n − 1) = 2n−1 − 1 then T(n) = 2(2n−1 − 1) + 1 = 2n − 1.
Why nothing does better. The recurrence only says what this method costs. The minimum comes from the largest disk. It has to move at least once, and at the moment it moves, every other disk must be on the one remaining peg, because none can sit under it and none can be on its source or target. Getting them there takes at least T(n − 1) moves. After it lands they all still have to come back on top of it, another T(n − 1). So any solution needs at least 2 T(n − 1) + 1, which is exactly what the recursion spends.
Play it yourself with a few extra moves and you will see the difference: every legal path works, but only one is this short.