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

Minimum moves: 7

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