DSAverse

Recursion

Loading Recursion Visualizer...

Recursion Tree

depth: 1

f(n) = f(n-1) + f(n-2)

DSAverse

Initializing Sorting Algorithms...

Sorting

Trees

Graphs

Preparing interactive visualizations...

Back to Recursion

Tower of Hanoi

Three elegant recursive steps solve an exponentially hard puzzle. Watch divide & conquer in action.

Divide & Conquer

O(2^n) Time

7 Optimal Moves

Controls

Disks: 3 (min moves: 7)

Speed: 1200ms

Move Information

Progress1/0

Moves:0/7

Phase:START

Depth:0

Adjust disks and click Play.

Call:

Test Yourself

Q1/3

What are the 3 recursive steps of Tower of Hanoi (n disks, A→C using B)?

Tower of Hanoi Puzzle

A (Source)

B (Auxiliary)

C (Destination)

Rules

Move all disks from Tower A to Tower C
Only move one disk at a time
Never place a larger disk on a smaller disk
Use Tower B as auxiliary space

2 disks

3 moves

3 disks

7 moves

4 disks

15 moves

5 disks

31 moves

6 disks

63 moves

Algorithm Analysis

Complexity

Time: O(2^n) — doubles per disk
Space: O(n) — recursion depth
Moves: 2^n - 1 (optimal)
64 disks → 584 billion years!

Recurrence

T(1) = 1
T(n) = 2T(n-1) + 1
Solution: T(n) = 2^n - 1

Applications

Backup tape rotation strategies
Recursive algorithm education
Puzzle game mechanics
Mathematical sequence analysis
Divide & conquer methodology
History: Édouard Lucas (1883)

Python

def tower_of_hanoi(n, source, destination, auxiliary):
    if n == 1:
        print(f"Move disk 1: {source} -> {destination}")
        return
    # Step 1: Move n-1 disks out of the way
    tower_of_hanoi(n-1, source, auxiliary, destination)
    # Step 2: Move the largest disk
    print(f"Move disk {n}: {source} -> {destination}")
    # Step 3: Move n-1 disks to destination
    tower_of_hanoi(n-1, auxiliary, destination, source)

# 3 disks: 7 total moves

JavaScript

function towerOfHanoi(n, source, destination, auxiliary) {
    if (n === 1) {
        console.log(`Move disk 1: ${source} → ${destination}`);
        return;
    }
    towerOfHanoi(n-1, source, auxiliary, destination);
    console.log(`Move disk ${n}: ${source} → ${destination}`);
    towerOfHanoi(n-1, auxiliary, destination, source);
}
// 3 disks → 7 moves

DSAverse

Recursion

Loading Recursion Visualizer...

Recursion Tree

depth: 1

f(n) = f(n-1) + f(n-2)

Back to Recursion

Tower of Hanoi

Three elegant recursive steps solve an exponentially hard puzzle. Watch divide & conquer in action.

Divide & Conquer

O(2^n) Time

7 Optimal Moves

Controls

Disks: 3 (min moves: 7)

Speed: 1200ms

Move Information

Progress1/0

Moves:0/7

Phase:START

Depth:0

Adjust disks and click Play.

Call:

Test Yourself

Q1/3

What are the 3 recursive steps of Tower of Hanoi (n disks, A→C using B)?

Tower of Hanoi Puzzle

A (Source)

B (Auxiliary)

C (Destination)

Rules

Move all disks from Tower A to Tower C
Only move one disk at a time
Never place a larger disk on a smaller disk
Use Tower B as auxiliary space

2 disks

3 moves

3 disks

7 moves

4 disks

15 moves

5 disks

31 moves

6 disks

63 moves

Algorithm Analysis

Complexity

Time: O(2^n) — doubles per disk
Space: O(n) — recursion depth
Moves: 2^n - 1 (optimal)
64 disks → 584 billion years!

Recurrence

T(1) = 1
T(n) = 2T(n-1) + 1
Solution: T(n) = 2^n - 1

Applications

Backup tape rotation strategies
Recursive algorithm education
Puzzle game mechanics
Mathematical sequence analysis
Divide & conquer methodology
History: Édouard Lucas (1883)

Python

def tower_of_hanoi(n, source, destination, auxiliary):
    if n == 1:
        print(f"Move disk 1: {source} -> {destination}")
        return
    # Step 1: Move n-1 disks out of the way
    tower_of_hanoi(n-1, source, auxiliary, destination)
    # Step 2: Move the largest disk
    print(f"Move disk {n}: {source} -> {destination}")
    # Step 3: Move n-1 disks to destination
    tower_of_hanoi(n-1, auxiliary, destination, source)

# 3 disks: 7 total moves

JavaScript

function towerOfHanoi(n, source, destination, auxiliary) {
    if (n === 1) {
        console.log(`Move disk 1: ${source} → ${destination}`);
        return;
    }
    towerOfHanoi(n-1, source, auxiliary, destination);
    console.log(`Move disk ${n}: ${source} → ${destination}`);
    towerOfHanoi(n-1, auxiliary, destination, source);
}
// 3 disks → 7 moves