Towers of Hanoi
Towers of Hanoi moves n discs from one peg to another, using a third peg as a spare, under the rule that a larger disc may never sit on a smaller one. The recursive solution moves the top n − 1 discs onto the spare peg, moves the single largest disc directly to its destination, then moves the n − 1 discs from the spare peg onto the destination, on top of the disc that just arrived.
When it is the right choice
Towers of Hanoi is not a problem anyone needs to solve outside a classroom, but the recursive solution is provably optimal: it is impossible to solve n discs in fewer than 2ⁿ − 1 moves, and this solution makes exactly that many. Its value here is structural — it is the first algorithm on this page whose recursive calls do real work both before and after the call they make, rather than only building toward a base case.
How it works
- Call hanoi with the number of discs to move, the peg to move them from, the peg to move them to, and the spare peg to use.
- If there is only one disc, move it straight from its peg to its destination and hand back.
- Otherwise, call hanoi to move the top n − 1 discs from the starting peg onto the spare peg.
- Move the single largest disc from the starting peg to the destination peg.
- Call hanoi to move the n − 1 discs now on the spare peg onto the destination peg, on top of the disc that just arrived.
Worth noticing
- Depth and call count pull apart here for the first time on this page: five discs need a stack only five deep, but make 31 calls getting there — depth measures how far down the recursion goes, not how much work it does.
- The move between the two recursive calls is the "on the way up as well as down" lesson: everything before it happens while the discs are still being uncovered, and the one thing this call actually does to the pegs happens in the middle, not at the top or the bottom.
- The pegs view exists because this is the one algorithm on this page whose picture is not really about the call stack at all — it is three columns of discs, and the recursion is how they get rearranged.
Cost
- Best
- O(2ⁿ)
- Average
- O(2ⁿ)
- Worst
- O(2ⁿ)
- Extra space
- O(n)
- Largest input
- n = 8
The largest input is a pedagogical ceiling rather than a technical one. This algorithm makes 2ⁿ − 1 calls, and past n = 8 the run stops being something a person can sit and watch — long before it reaches the step limit the tool enforces.