Tower of Hanoi

This puzzle is the clearest possible introduction to recursion — the idea of solving a problem by solving a smaller version of itself. Master it and you can immediately step into Recursive Thinking, Base Cases and Recurrence, Depth-First Search with Backtracking, and Stack Memory Behaviour. It also shows you, dramatically, why an elegant solution can still be an expensive one — which is the foundation for understanding complexity in AI systems, from training large models to searching game trees.

Imagine three pegs and a stack of disks, each disk smaller than the one below it. The goal is to move the entire stack from the left peg to the right peg, moving one disk at a time, and never placing a larger disk on top of a smaller one. There are no other rules; you can use the middle peg as a spare. The puzzle feels like it should be complicated, but there is a simple recipe that solves it for any number of disks, and that recipe is recursion. The key insight is this: the biggest disk is the only one that must move directly from the start peg to the goal peg, and everything else just needs to get out of the way first. So instead of thinking about all the disks at once, you think only about the bottom one. To move a stack of n disks from peg A to peg B using peg C, you first move the top n-1 disks from A to C (using B as the spare), then move the biggest disk from A to B, then move the n-1 disks from C to B (using A as the spare). That is the whole puzzle. The recipe repeats for the smaller stacks, and each repetition is the same action, just with fewer disks. That is exactly what recursion is: a procedure that calls itself on a smaller problem, until the problem is so small it can be solved directly (here, moving one disk is trivial). Once you accept that the smaller problem will be handled correctly, the whole stack moves almost effortlessly — the recursive call does the heavy lifting.

Think of a large office move. You have a filing cabinet with many drawers, and the whole cabinet needs to go to a new building across town. The biggest, heaviest drawer is at the bottom, and it can only be moved when everything above it has been taken out and set aside on a table (the spare peg). So the moving plan goes like this: first, pack and move all the top drawers to the table, but in a way that respects their stacking order (you can't put a heavier drawer on a lighter one, because it would crush it). Then move the big heavy drawer to the new building. Then, move the top drawers back from the table to the new building, again keeping their order. That is the whole plan, and it applies recursively: moving the top drawers to the table is itself the same problem, just with fewer drawers. The analogy works well, but it has its limits: in the office, you could hire more people, or use a lift; in the puzzle, the rules are absolute. Also, the puzzle assumes you can use the spare peg freely; in an office you might not have enough space. The key point is the recursive structure: the plan for n drawers is built on the plan for n-1 drawers, and the biggest drawer is the anchor that everything else revolves around.

The Tower of Hanoi is a puzzle where you move a stack of disks between three pegs, one at a time, never placing a larger disk on a smaller one; its solution is a three-line recursive function that moves n-1 disks, then the largest, then n-1 disks again, and the minimum number of moves required is 2^n - 1.

You have not studied any other topics yet, so this is your first formal concept. However, this concept introduces recursion, which you will soon connect to Recursive Thinking (naming the base case and the shrinking argument before the recursive call), Base Cases and Recurrence (the terminating condition and the rule that relate a case to smaller ones), and Stack Memory Behaviour (each recursive call consumes a stack frame, so deep recursion can overflow the stack). It also lays the groundwork for Depth-First Search with Backtracking and Tail Recursion, which you will study later.