Tower of Hanoi
Tower of Hanoi is a classic mathematical puzzle invented by French mathematician Édouard Lucas in 1883. The puzzle consists of three rods and n disks of different sizes that can slide onto any rod. The objective is to move the entire stack from one rod to another, following rules: (1) only one disk can be moved at a time, (2) only the top disk from any rod can be moved, (3) a larger disk cannot be placed on a smaller disk. The elegant recursive solution requires exactly 2^n - 1 moves.
Visualization
Interactive visualization for Tower of Hanoi
Tower of Hanoi Visualization
Classic recursion problem: Move all disks from left to right tower using middle as auxiliary
Time Complexity: O(2n)
Space Complexity: O(n) recursion depth
Recurrence: T(n) = 2T(n-1) + 1
Rules:
- Move one disk at a time
- Larger disk cannot be on smaller disk
- Only top disk can be moved
- Minimum moves = 2n - 1
Interactive visualization with step-by-step execution
Implementation
1function towerOfHanoi(n: number, from: string = 'A', to: string = 'C', aux: string = 'B'): void {
2 if (n === 1) {
3 console.log(`Move disk 1 from ${from} to ${to}`);
4 return;
5 }
6
7 towerOfHanoi(n - 1, from, aux, to);
8 console.log(`Move disk ${n} from ${from} to ${to}`);
9 towerOfHanoi(n - 1, aux, to, from);
10}
11
12// With move counting
13function towerOfHanoiMoves(n: number): number {
14 if (n === 1) return 1;
15 return 2 * towerOfHanoiMoves(n - 1) + 1;
16}
17
18// Iterative solution (advanced)
19function towerOfHanoiIterative(n: number): void {
20 const totalMoves = Math.pow(2, n) - 1;
21 const src = 'A', dest = 'C', aux = 'B';
22
23 for (let i = 1; i <= totalMoves; i++) {
24 if (i % 3 === 1) {
25 console.log(`Move disk from ${src} to ${dest}`);
26 } else if (i % 3 === 2) {
27 console.log(`Move disk from ${src} to ${aux}`);
28 } else {
29 console.log(`Move disk from ${aux} to ${dest}`);
30 }
31 }
32}Deep Dive
Theoretical Foundation
Tower of Hanoi perfectly demonstrates recursion and mathematical induction. The solution is recursive: to move n disks from source to destination using auxiliary, we (1) move n-1 disks from source to auxiliary (recursive call), (2) move largest disk from source to destination (base operation), (3) move n-1 disks from auxiliary to destination (recursive call). Base case: moving 1 disk is trivial. The number of moves T(n) = 2T(n-1) + 1, which solves to 2^n - 1. This is optimal - no algorithm can solve it in fewer moves. The puzzle has applications in backup rotation, algorithm analysis, and teaching recursion.
Complexity
Time
O(2^n)
O(2^n)
O(2^n)
Space
O(n) recursion stack
Applications
Industry Use
Teaching recursion in computer science courses
Backup rotation strategies (Grandfather-Father-Son)
Algorithm analysis and complexity theory
Puzzle games and brain teasers
Understanding exponential growth
Job scheduling with dependencies
Use Cases
Related Algorithms
Generate All Permutations
Generate all possible arrangements (permutations) of n distinct elements. For n elements, there are exactly n! permutations. This classic backtracking problem demonstrates recursive exploration of the solution space, where we systematically build permutations by choosing elements and backtracking when complete. Used in combinatorics, constraint satisfaction, and optimization problems.
Generate All Combinations
Generate all C(n,k) combinations - all possible selections of k elements from n elements where order doesn't matter. Unlike permutations, {1,2,3} and {3,2,1} are the same combination. Uses backtracking to explore choices systematically, ensuring each combination is counted once. Fundamental in statistics, probability, lottery systems, and feature selection in machine learning.
Generate All Subsets (Power Set)
Generate the power set - all 2^n possible subsets of an n-element set, including the empty set and the set itself. For example, subsets of {1,2,3} are: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}. Can be elegantly solved using recursion, iteration, or bit manipulation. Essential in combinatorial optimization and constraint satisfaction.
Quicksort
A highly efficient, in-place sorting algorithm that uses divide-and-conquer strategy. Invented by Tony Hoare in 1959, it remains one of the most widely used sorting algorithms due to its excellent average-case performance and cache efficiency.