JavaScript Program for Tower of Hanoi with Output

A JavaScript program for Tower of Hanoi uses a recursive function like function towerOfHanoi(n, from, to, aux) { if (n === 1) { console.log(`Move disk 1 from ${from} to ${to}`); return; } towerOfHanoi(n-1, from, aux, to); console.log(`Move disk ${n} from ${from} to ${to}`); towerOfHanoi(n-1, aux, to, from); } to print the steps to move disks.

Examples

Inputn = 1

OutputMove disk 1 from A to C

Inputn = 2

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

Inputn = 3

OutputMove 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

How to Think About It

To solve Tower of Hanoi, think about moving the top n-1 disks to the auxiliary peg first, then moving the largest disk to the target peg, and finally moving the n-1 disks from auxiliary to target. Use recursion to repeat this process until only one disk remains, which can be moved directly.

Algorithm

1

If there is only one disk, move it directly from source to target.

2

Otherwise, move n-1 disks from source to auxiliary peg using target as helper.

3

Move the nth (largest) disk from source to target peg.

4

Move the n-1 disks from auxiliary peg to target peg using source as helper.

Code

javascript

function towerOfHanoi(n, from, to, aux) {
  if (n === 1) {
    console.log(`Move disk 1 from ${from} to ${to}`);
    return;
  }
  towerOfHanoi(n - 1, from, aux, to);
  console.log(`Move disk ${n} from ${from} to ${to}`);
  towerOfHanoi(n - 1, aux, to, from);
}

const n = 3;
towerOfHanoi(n, 'A', 'C', 'B');

Output

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

Dry Run

Let's trace the Tower of Hanoi program for n=2 disks moving from peg A to peg C using peg B as auxiliary.

1

Move n-1 disks from A to B

Move disk 1 from A to B

2

Move disk 2 from A to C

Move disk 2 from A to C

3

Move n-1 disks from B to C

Move disk 1 from B to C

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

Why This Works

Step 1: Base Case

When there is only one disk (n === 1), move it directly from the source peg to the target peg.

Step 2: Recursive Step 1

Move the top n-1 disks from the source peg to the auxiliary peg, freeing the largest disk.

Step 3: Move Largest Disk

Move the largest disk from the source peg to the target peg.

Step 4: Recursive Step 2

Move the n-1 disks from the auxiliary peg to the target peg.

Alternative Approaches

Iterative approach using stack

javascript

function towerOfHanoiIterative(n, from, to, aux) {
  const totalMoves = Math.pow(2, n) - 1;
  const pegs = { A: [], B: [], C: [] };
  for (let i = n; i >= 1; i--) pegs[from].push(i);
  const moveDisk = (src, dest) => {
    if (pegs[src].length === 0) {
      pegs[src].push(pegs[dest].pop());
      console.log(`Move disk ${pegs[src][pegs[src].length-1]} from ${dest} to ${src}`);
    } else if (pegs[dest].length === 0) {
      pegs[dest].push(pegs[src].pop());
      console.log(`Move disk ${pegs[dest][pegs[dest].length-1]} from ${src} to ${dest}`);
    } else if (pegs[src][pegs[src].length-1] > pegs[dest][pegs[dest].length-1]) {
      pegs[src].push(pegs[dest].pop());
      console.log(`Move disk ${pegs[src][pegs[src].length-1]} from ${dest} to ${src}`);
    } else {
      pegs[dest].push(pegs[src].pop());
      console.log(`Move disk ${pegs[dest][pegs[dest].length-1]} from ${src} to ${dest}`);
    }
  };
  let s = from, d = to, a = aux;
  if (n % 2 === 0) [d, a] = [a, d];
  for (let i = 1; i <= totalMoves; i++) {
    if (i % 3 === 1) moveDisk(s, d);
    else if (i % 3 === 2) moveDisk(s, a);
    else moveDisk(a, d);
  }
}

// Usage example:
towerOfHanoiIterative(3, 'A', 'C', 'B');

This iterative method uses stacks and simulates moves without recursion but is more complex to understand.

Complexity: O(2^n) time, O(n) space

Time Complexity

The algorithm makes 2^n - 1 moves, so time complexity is exponential, O(2^n). Each move is printed once.

Space Complexity

The recursion stack depth is n, so space complexity is O(n). No extra large data structures are used.

Which Approach is Fastest?

Recursive and iterative approaches have the same time complexity, but recursion is simpler and clearer for beginners.

Approach	Time	Space	Best For
Recursive	O(2^n)	O(n)	Clarity and simplicity
Iterative (stack)	O(2^n)	O(n)	Avoiding recursion, complex control