Tower of Hanoi

📌 Definition:

📖 Detailed Explanation:

Classic recursion: move n-1 disks to the auxiliary peg, move the largest disk to the destination, then move the n-1 disks from auxiliary to destination. It requires exactly 2^n - 1 moves — O(2^n), an intrinsic property of the problem, not an inefficiency.

💻 Solutions:

• Java
• JavaScript
• Python

public static void hanoi(int n, char from, char aux, char to) {
    if (n == 1) { System.out.println("Move disk 1 from " + from + " to " + to); return; }
    hanoi(n - 1, from, to, aux);
    System.out.println("Move disk " + n + " from " + from + " to " + to);
    hanoi(n - 1, aux, from, to);
}

function hanoi(n, from, aux, to) {
  if (n === 1) { console.log('Move disk 1 from ' + from + ' to ' + to); return; }
  hanoi(n - 1, from, to, aux);
  console.log('Move disk ' + n + ' from ' + from + ' to ' + to);
  hanoi(n - 1, aux, from, to);
}

def hanoi(n, frm, aux, to):
    if n == 1:
        print(f'Move disk 1 from {frm} to {to}')
        return
    hanoi(n - 1, frm, to, aux)
    print(f'Move disk {n} from {frm} to {to}')
    hanoi(n - 1, aux, frm, to)

🔑 Key Points:

• Recurse: move n-1 to aux, move 1, move n-1 to dest
• Base case: n == 1 moves a single disk
• Requires 2^n - 1 moves (O(2^n))
• Exponential is inherent, not a bug

🌍 Real-World Example: