Recursion & Backtracking

Peg A (Source)

Peg C (Destination)

Peg B (Auxiliary)

Debugger · v1.0

LIVE

1function hanoi(n, from, to, aux) {

2 // 1: Base Case

3 if (n === 0) return;

5 // 2: Recurse n-1 disks: from -> aux

6 hanoi(n - 1, from, aux, to);

8 // 3: Move disk n: from -> to

9 moveDisk(n, from, to);

11 // 4: Recurse n-1 disks: aux -> to

12 hanoi(n - 1, aux, to, from);

13}

Debugger · v1.0

LIVE

1function hanoi(n, from, to, aux) {

2 // 1: Base Case

3 if (n === 0) return;

5 // 2: Recurse n-1 disks: from -> aux

6 hanoi(n - 1, from, aux, to);

8 // 3: Move disk n: from -> to

9 moveDisk(n, from, to);

11 // 4: Recurse n-1 disks: aux -> to

12 hanoi(n - 1, aux, to, from);

13}

State Inspector

Variable	Value
$n	3

Disks:3

Recursion & Backtracking

Tower of Hanoi

Step 1 of 6

A mathematical puzzle where we move a stack of disks from one rod to another, following simple recursive rules.

The Rules

1) Only one disk can be moved at a time. 2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack. 3) No larger disk may be placed on top of a smaller disk.