Tower of Hanoi (recursion)

Medium TimeO(2ⁿ) SpaceO(n)

Three pegs hold a stack of disks of decreasing size, all on the first. The whole stack has to reach a target peg, moved one disk at a time and only ever the top disk of a peg, and a larger disk may never sit on a smaller one. All three pegs may be used. Given n disks and the three peg names, return the number of moves the transfer takes.

Examples

Example 1

Input
n = 3from = "A"to = "C"via = "B"
Output
7
Three disks from A to C, using B, in 2³ − 1 moves.

Example 2

Input
n = 4from = "A"to = "C"via = "B"
Output
15
One more disk doubles the count and adds one: 2⁴ − 1.

The Code

function hanoi(n, from, to, via) {
  if (n === 0) return 0;
  const moves1 = hanoi(n - 1, from, via, to);
  const moves2 = hanoi(n - 1, via, to, from);
  return moves1 + 1 + moves2;
}
hanoi(3, "A", "C", "B");
Done

The first 11 calls, of 15. This one does not fit on a page.

Step through hanoi(3, "A", "C", "B") call by call

More like this

All recursion examples (13) →