Tower of Hanoi from scratch: the four-line recursion behind 2^n-1 moves

Day 27 of my "build a small game a day, from nothing" run. Today is the one every CS course wheels out to explain recursion, and for good reason: Tower of Hanoi is a puzzle you can hold in your head, yet its solver is four lines that call themselves and always play the perfect game.

Play it (and read the LOOK / UNDERSTAND / BUILD tabs) here: https://dev48v.infy.uk/game/day27-tower-of-hanoi.html

The puzzle

Three pegs. A stack of disks on the left, biggest on the bottom, smallest on top. Move the whole stack to the right peg with two rules that never bend: move one disk at a time, and never put a bigger disk on a smaller one. That second rule is the entire difficulty. Without it you'd just carry the pile across.

Strip it down to arrays

The trap is picturing wooden pegs. Don't. A peg is an array of disk sizes, ordered bottom to top, so the last element is the disk on top — the only one you're ever allowed to touch.

let pegs = [[], [], []];
for (let s = N; s >= 1; s--) pegs[0].push(s);  // [N, ..., 2, 1] on the left
const top = p => pegs[p][pegs[p].length - 1];

A move is a push(pop()). The only interesting part is whether it's allowed, and that's one boolean:

function canMove(from, to){
  if (from === to || !pegs[from].length) return false;
  return pegs[to].length === 0 || top(to) > top(from);  // empty, or bigger on top
}

Because that check runs before the push, an illegal move never happens. There's nothing to undo, no error state to clean up. The same function refs both the human clicking pegs and the auto-solver.

The four lines

Here's the part worth the price of admission. Pretend you already know how to move a stack of n-1 disks anywhere. Then moving n disks from A to C is trivial:

1. Move the top n-1 disks onto the spare peg B.
2. Move the one biggest disk from A to C.
3. Move those n-1 disks from B onto C.

You never actually solved step 1 by hand — you assumed it and let the function call itself on a smaller problem. That leap of faith is recursion.

function solve(n, from, to, via, out){
  if (n === 0) return;               // base case: no disks, no moves
  solve(n - 1, from, via, to, out);  // clear the top off
  out.push([from, to]);              // move the big disk
  solve(n - 1, via, to, from, out);  // pile them back on
}

Notice it doesn't touch the pegs. It pushes each move into a list. That separation — compute the plan, then play the plan — is the single best decision in the whole thing. The solver stays pure and testable; the animation is just something that consumes its output on a timer.

Why exactly 2^n - 1, and never fewer

Count what the recursion costs. Solving n disks is: solve n-1, one big-disk move, solve n-1 again.

T(n) = 2·T(n-1) + 1,  T(0) = 0   ⇒   T(n) = 2^n - 1

And it isn't just what this method spends — it's the floor. The biggest disk has to move at least once, and before it can, all n-1 smaller disks must be parked on the spare peg, which itself takes a full 2^(n-1) - 1 moves, then the same again to rebuild. So 7 for three disks, 15 for four, 255 for eight. The legend about 64 golden disks ending the world? That's 2^64 - 1 moves — at one a second, about 585 billion years. The universe is safe.

I wired the page to show your move count next to 2^n - 1 live, so matching it feels earned.

Playing the plan back

Auto-solve resets the board, grabs the move list, and steps through it:

const list = []; solve(N, 0, 2, 1, list);       // via = the third peg
let k = 0, timer = setInterval(() => {
  if (k >= list.length){ clearInterval(timer); return; }
  const [f, t] = list[k++]; doMove(f, t); render();
}, dt);

I scaled the tick to the number of moves so a 3-disk solve is leisurely and a 255-move 8-disk solve still wraps in a few seconds.

The bit that surprised me

Recursion is the clearest solution here, but not the only one. There's a no-stack trick: number the moves 1, 2, 3... and the disk you move on move k is decided by the lowest set bit of k. Move 1 (001) → disk 1, move 2 (010) → disk 2, move 4 (100) → disk 3. Same 2^n - 1 moves, zero recursion. One problem, two completely different-looking correct answers — a good reminder not to fall in love with the first shape a solution takes.

Whole thing is vanilla JS, no libraries, runs offline. Tomorrow: Flood-It.