DSAverse

Initializing Sorting Algorithms...

Sorting Algorithm

Binary Tree

Graph Traversal

Preparing interactive visualizations for optimal learning experience...

DSAverse

Initializing Sorting Algorithms...

Sorting Algorithm

Binary Tree

Graph Traversal

Preparing interactive visualizations for optimal learning experience...

Back to Recursion

Tower of Hanoi

Watch the classic divide & conquer algorithm solve the ancient Tower of Hanoi puzzle with elegant recursive moves.

Divide & Conquer

O(2^n) Time

7 Optimal Moves

Controls

Number of Disks: 3

Minimum moves: 7

Speed: 1200ms

Move Information

Current Move:0/7

Phase: START

Recursion Depth: 0

Current Step

Step 1 of 0

Click Start to begin solving the Tower of Hanoi puzzle

Subproblem:

Call:

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

Python Implementation

def tower_of_hanoi(n, source, destination, auxiliary):
    if n == 1:
        # Base case: move single disk
        print(f"Move disk 1 from {source} to {destination}")
        return
    
    # Step 1: Move n-1 disks from source to auxiliary
    tower_of_hanoi(n-1, source, auxiliary, destination)
    
    # Step 2: Move the largest disk from source to destination  
    print(f"Move disk {n} from {source} to {destination}")
    
    # Step 3: Move n-1 disks from auxiliary to destination
    tower_of_hanoi(n-1, auxiliary, destination, source)

# Solve 3-disk Tower of Hanoi
tower_of_hanoi(3, 'A', 'C', 'B')
# Total moves: 7

JavaScript Implementation

function towerOfHanoi(n, source, destination, auxiliary) {
    if (n === 1) {
        console.log(`Move disk 1 from ${source} to ${destination}`);
        return;
    }
    
    // Move n-1 disks to auxiliary
    towerOfHanoi(n-1, source, auxiliary, destination);
    
    // Move largest disk to destination
    console.log(`Move disk ${n} from ${source} to ${destination}`);
    
    // Move n-1 disks to destination
    towerOfHanoi(n-1, auxiliary, destination, source);
}

// Solve 3-disk puzzle
towerOfHanoi(3, 'A', 'C', 'B'); // 7 moves

Algorithm Analysis

Complexity Analysis

• Time Complexity: O(2^n)
• Space Complexity: O(n) recursion depth
• Moves Required: 2^n - 1 (optimal)
• Growth: Doubles with each disk added
• Legend: 64 disks would take 584 billion years!

Mathematical Properties

• Recurrence: T(n) = 2T(n-1) + 1
• Base case: T(1) = 1
• Solution: T(n) = 2^n - 1
• Perfect example of exponential growth

Real-World Applications

• Backup Systems: Tape rotation strategies
• Computer Science: Recursive algorithm teaching
• Game Development: Puzzle game mechanics
• Mathematics: Recursive sequence analysis
• Problem Solving: Divide & conquer methodology

Historical Context

• Ancient puzzle from Indian temples
• Popularized by mathematician Édouard Lucas (1883)
• Classic introduction to recursion concepts
• Demonstrates elegant mathematical beauty

DSAverse

Initializing Sorting Algorithms...

Sorting Algorithm

Binary Tree

Graph Traversal

Preparing interactive visualizations for optimal learning experience...

Back to Recursion

Tower of Hanoi

Watch the classic divide & conquer algorithm solve the ancient Tower of Hanoi puzzle with elegant recursive moves.

Divide & Conquer

O(2^n) Time

7 Optimal Moves

Controls

Number of Disks: 3

Minimum moves: 7

Speed: 1200ms

Move Information

Current Move:0/7

Phase: START

Recursion Depth: 0

Current Step

Step 1 of 0

Click Start to begin solving the Tower of Hanoi puzzle

Subproblem:

Call:

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

Python Implementation

def tower_of_hanoi(n, source, destination, auxiliary):
    if n == 1:
        # Base case: move single disk
        print(f"Move disk 1 from {source} to {destination}")
        return
    
    # Step 1: Move n-1 disks from source to auxiliary
    tower_of_hanoi(n-1, source, auxiliary, destination)
    
    # Step 2: Move the largest disk from source to destination  
    print(f"Move disk {n} from {source} to {destination}")
    
    # Step 3: Move n-1 disks from auxiliary to destination
    tower_of_hanoi(n-1, auxiliary, destination, source)

# Solve 3-disk Tower of Hanoi
tower_of_hanoi(3, 'A', 'C', 'B')
# Total moves: 7

JavaScript Implementation

function towerOfHanoi(n, source, destination, auxiliary) {
    if (n === 1) {
        console.log(`Move disk 1 from ${source} to ${destination}`);
        return;
    }
    
    // Move n-1 disks to auxiliary
    towerOfHanoi(n-1, source, auxiliary, destination);
    
    // Move largest disk to destination
    console.log(`Move disk ${n} from ${source} to ${destination}`);
    
    // Move n-1 disks to destination
    towerOfHanoi(n-1, auxiliary, destination, source);
}

// Solve 3-disk puzzle
towerOfHanoi(3, 'A', 'C', 'B'); // 7 moves

Algorithm Analysis

Complexity Analysis

• Time Complexity: O(2^n)
• Space Complexity: O(n) recursion depth
• Moves Required: 2^n - 1 (optimal)
• Growth: Doubles with each disk added
• Legend: 64 disks would take 584 billion years!

Mathematical Properties

• Recurrence: T(n) = 2T(n-1) + 1
• Base case: T(1) = 1
• Solution: T(n) = 2^n - 1
• Perfect example of exponential growth

Real-World Applications

• Backup Systems: Tape rotation strategies
• Computer Science: Recursive algorithm teaching
• Game Development: Puzzle game mechanics
• Mathematics: Recursive sequence analysis
• Problem Solving: Divide & conquer methodology

Historical Context

• Ancient puzzle from Indian temples
• Popularized by mathematician Édouard Lucas (1883)
• Classic introduction to recursion concepts
• Demonstrates elegant mathematical beauty