Tower of Hanoi in JavaScript

Run it yourself

Save the listing as hanoi.js and run it:

node hanoi.js

It prints the seven moves of the three-disk puzzle:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Change the 3 in the call to solve a bigger puzzle. Every disk you add doubles the output, plus one line.

Line by line

Not what each line says — the listing says that — but why it has to be there:

Why those three lines are enough — the correctness proof, the recurrence and the complexity — is on the Tower of Hanoi algorithm page, and holds for every language here.

Numbers that are not quite integers

// A Number is a 64-bit float: every integer is exact only up to 2 ** 53.
const asNumber = 2 ** 64 - 1;

// A BigInt is exact at any size. Every literal needs the n suffix.
function minimumMoves(n) {
  return 2n ** BigInt(n) - 1n;
}

console.log(`Number: ${asNumber}`);
console.log(`BigInt: ${minimumMoves(64)}`);

node count-moves.js

Number: 18446744073709552000
BigInt: 18446744073709551615

Every JavaScript Number is a 64-bit floating-point value, and floating point represents integers exactly only up to 2⁵³ − 1, which is Number.MAX_SAFE_INTEGER. The 64-disk move count is far past that, so 2 ** 64 - 1 cannot be stored: the subtraction is lost to rounding, the result is 2⁶⁴ itself, and it prints as 18446744073709552000, which is simply the shortest decimal that names that float. There is no error and no warning — only a number that is wrong in its last digits.

BigInt holds integers of any size exactly. The price is an n on every literal and no mixing of the two kinds: 2n ** 64n - 1 throws a TypeError, because that 1 is a Number. The calculator on this site does all of its arithmetic in BigInt for exactly this reason.

One move at a time, with a generator

function* hanoi(n, source, target, spare) {
  if (n === 0) {
    return;
  }
  yield* hanoi(n - 1, source, spare, target);
  yield { disk: n, from: source, to: target };
  yield* hanoi(n - 1, spare, target, source);
}

// Nothing runs until a move is asked for, so the caller sets the pace.
const moves = hanoi(3, "A", "C", "B");
for (const { disk, from, to } of moves) {
  console.log(`Move disk ${disk} from ${from} to ${to}`);
}

node hanoi-generator.js

A function written function* is a generator. Calling it runs nothing; each call to next() runs it only as far as the next yield, and the value yielded comes back as the result. yield* hands control to another generator — here, the recursive call — until that one runs out.

The for...of loop at the bottom asks for every move straight away, but nothing forces it to. A page can instead call moves.next() from a timer or a button and draw one move per tick, while the recursion waits, call stack and all, exactly where it stopped. That makes the generator the natural shape for an animation: the solver and the drawing stay separate, and neither has to know about the other’s timing.

There is a cost. A move made deep in the recursion is passed up through every yield* above it, so each move takes work proportional to the depth of the call that made it — O(n) rather than O(1). At any size small enough to animate, that is far too little to notice.

A disk count that is not a whole number

JavaScript has no integer type, so nothing stops hanoi(2.5, "A", "C", "B") from being called — and a count like that never reaches the base case:

• 2.5 counts down 2.5, 1.5, 0.5, −0.5 and on, stepping clean over zero.
• A negative count does the same from a different start.
• A string read from a form field works or fails by accident: "3" works, because n - 1 turns it into a Number on the first call, but "0" never equals 0 under ===.

All three recurse until the engine gives up with RangeError: Maximum call stack size exceeded.

So when a Tower of Hanoi function throws that RangeError, the base case is being missed — the recursion is almost never too deep. It is only n + 1 calls deep, and nobody waits for a puzzle big enough to fill the stack. The typed languages on this site stop the commonest version before the program runs: Java and C# refuse to compile a double passed as an int, while C and C++ quietly truncate 2.5 to 2 and solve a smaller puzzle, without a warning even under -Wall -Wextra. In JavaScript the check belongs at the door rather than in the recursion: test Number.isInteger(n) && n >= 0 once, before the first call.

The same algorithm in other languages

• Tower of Hanoi in PythonRecursive and iterative programs, why Python's recursion limit never bites here, and integers that simply do not overflow.
• Tower of Hanoi in JavaWhy (1L << 64) − 1 is zero, counting with BigInteger, and the same solution driven by an explicit stack.
• Tower of Hanoi in CUndefined shifts, uint64_t, and a loop that reads every move straight off the bits of the move number.
• Tower of Hanoi in C++Collecting the moves in a std::vector, the 64-disk count checked by the compiler, and three pairs of towers in a loop.
• Tower of Hanoi in C#Top-level statements, an iterator whose moves LINQ can query, and ulong, checked arithmetic and UInt128 for the move count.

Frequently asked questions