Skip to the content
Start

Project: tower of Hanoi

JavaScript · Unit 11: Recursion

In the tower of Hanoi there are three pegs and a stack of disks, from the biggest at the bottom to the smallest at the top. You have to move it from peg A to peg C, one disk at a time, never putting a big disk on a small one.

The trick is recursive: to move n disks, you move the top n - 1 to the spare peg, move the big disk to its place, and put the n - 1 back on top of it. With 0 disks, there's nothing to do.

function hanoi(n, from, to, spare) {
  if (n === 0) {
    return;
  }
  hanoi(n - 1, from, spare, to);
  console.log(`${from} to ${to}`);
  hanoi(n - 1, spare, to, from);
}
hanoi(3, "A", "C", "B");

Prints

A to C
A to B
C to B
A to C
B to A
B to C
A to C

Exercises in this lesson

You do them in the app, which checks them on the spot and explains why.

  1. 1. Multiple choice

    To move a tower of 4 disks, how many times do you have to move the 3-disk tower sitting on top of the big one?

  2. 2. Complete the code

    Fill in hanoi so it prints the 3 moves for a tower of 2 disks.

  3. 3. Write the code

    Write moves(n), which returns how many moves it takes to move a tower of n disks. Use recursion: with 0 disks it's 0 moves, and with n disks it's the moves for moving the n - 1 tower twice, plus one.

  4. 4. Write the code

    Now write movesLoop(n) with a loop, no recursion: start at 0 moves and, for each disk, the count becomes double plus one.

Do this lesson

It opens in your browser. This lesson is part of the full plan; the first unit of each course is free.

See all lessons →