Case Study 1: Tower of Hanoi and Recursive Thinking

The Legend

According to legend, in a temple in Hanoi, monks are transferring 64 golden disks from one diamond peg to another, using a third peg as an intermediary. The rules are simple:

  1. Only one disk may be moved at a time.
  2. Each move consists of taking the top disk from one peg and placing it on another.
  3. No disk may be placed on top of a smaller disk.

When the monks complete the transfer of all 64 disks, the world will end. (Fortunately, at one move per second, this takes about 585 billion years — roughly 42 times the current age of the universe.)

The Tower of Hanoi is the quintessential recursive problem. It is nearly impossible to solve iteratively without simulating the recursion, yet the recursive solution is breathtakingly simple: three lines of logic, no special data structures, no clever tricks. It is the problem that teaches you what recursion means.

The Recursive Insight

The key insight is this: to move N disks from peg A to peg C, you must:

  1. Move the top N − 1 disks from A to B (using C as a helper).
  2. Move the remaining bottom disk from A to C.
  3. Move the N − 1 disks from B to C (using A as a helper).

Steps 1 and 3 are smaller instances of the same problem. Step 2 is trivial — a single move. The base case is N = 0: there is nothing to move.

This is recursion at its purest. We solve a problem of size N by solving two problems of size N − 1 and doing one unit of direct work.

The Implementation

program TowerOfHanoi;

var
  MoveCount: Integer;

procedure Hanoi(N: Integer; Source, Target, Auxiliary: Char);
begin
  if N = 0 then
    Exit;

  { Step 1: Move N-1 disks from Source to Auxiliary }
  Hanoi(N - 1, Source, Auxiliary, Target);

  { Step 2: Move the bottom disk from Source to Target }
  Inc(MoveCount);
  WriteLn('Move ', MoveCount, ': Disk ', N,
          ' from ', Source, ' to ', Target);

  { Step 3: Move N-1 disks from Auxiliary to Target }
  Hanoi(N - 1, Auxiliary, Target, Source);
end;

begin
  MoveCount := 0;
  WriteLn('=== Tower of Hanoi ===');
  WriteLn;

  WriteLn('--- 3 Disks ---');
  MoveCount := 0;
  Hanoi(3, 'A', 'C', 'B');
  WriteLn('Total moves: ', MoveCount);
  WriteLn;

  WriteLn('--- 4 Disks ---');
  MoveCount := 0;
  Hanoi(4, 'A', 'C', 'B');
  WriteLn('Total moves: ', MoveCount);
end.

Sample Output (3 Disks)

--- 3 Disks ---
Move 1: Disk 1 from A to C
Move 2: Disk 2 from A to B
Move 3: Disk 1 from C to B
Move 4: Disk 3 from A to C
Move 5: Disk 1 from B to A
Move 6: Disk 2 from B to C
Move 7: Disk 1 from A to C
Total moves: 7

Analyzing the Recursion

The Call Tree for N = 3

Hanoi(3, A, C, B)
├── Hanoi(2, A, B, C)
│   ├── Hanoi(1, A, C, B)
│   │   ├── Hanoi(0, A, B, C) → returns
│   │   ├── Move Disk 1: A → C
│   │   └── Hanoi(0, B, C, A) → returns
│   ├── Move Disk 2: A → B
│   └── Hanoi(1, C, B, A)
│       ├── Hanoi(0, C, A, B) → returns
│       ├── Move Disk 1: C → B
│       └── Hanoi(0, A, B, C) → returns
├── Move Disk 3: A → C
└── Hanoi(2, B, C, A)
    ├── Hanoi(1, B, A, C)
    │   ├── Hanoi(0, B, C, A) → returns
    │   ├── Move Disk 1: B → A
    │   └── Hanoi(0, C, A, B) → returns
    ├── Move Disk 2: B → C
    └── Hanoi(1, A, C, B)
        ├── Hanoi(0, A, B, C) → returns
        ├── Move Disk 1: A → C
        └── Hanoi(0, B, C, A) → returns

Mathematical Properties

  • Number of moves for N disks: 2ᴺ − 1. For 3 disks: 7. For 4 disks: 15. For 64 disks: 18,446,744,073,709,551,615.
  • Maximum recursion depth: N (the depth of the call tree is exactly N).
  • Total function calls: 2ᴺ⁺¹ − 1 (including base cases).

The proof that 2ᴺ − 1 moves is both necessary and sufficient is a beautiful application of mathematical induction — itself a form of recursion in mathematics.

Why Iteration Fails

Try to write an iterative solution without looking up the algorithm. You will find it remarkably difficult. The iterative solution exists (it involves cycling disk 1 in a fixed pattern and making the only legal move for non-smallest disks), but it is unintuitive, error-prone, and much harder to verify. The recursive solution, by contrast, is almost self-evidently correct: if moving N − 1 disks works, then moving N disks clearly works.

Extensions and Variations

Counting Moves Without Printing

For large N, you only care about the count, not the individual moves:

function HanoiCount(N: Integer): Int64;
begin
  if N = 0 then
    HanoiCount := 0
  else
    HanoiCount := 2 * HanoiCount(N - 1) + 1;
end;

Of course, for this specific problem, we can compute the answer directly as 2ᴺ − 1. But the recursive formulation is more general and extends to variations of the puzzle.

Four-Peg Variant (Frame-Stewart Algorithm)

With four pegs instead of three, the optimal solution is conjectured (but not proven!) to use the Frame-Stewart algorithm: move the top k disks to a spare peg using all four pegs, move the remaining N − k disks using three pegs (standard Hanoi), then move the k disks to the destination using all four pegs. The optimal k depends on N, and this problem remains an open question in combinatorics.

Visualization

Adding a visual representation of the pegs transforms this from a console exercise into a satisfying demonstration:

procedure DrawPegs(const Pegs: array of TDiskStack);
var
  Row, Peg, DiskSize: Integer;
  MaxHeight: Integer;
begin
  MaxHeight := GetMaxHeight(Pegs);
  for Row := MaxHeight downto 1 do begin
    for Peg := 0 to 2 do begin
      DiskSize := GetDiskAtRow(Pegs[Peg], Row);
      if DiskSize = 0 then
        Write('    |    ')
      else
        Write(StringOfChar('=', DiskSize), '|',
              StringOfChar('=', DiskSize));
      Write('  ');
    end;
    WriteLn;
  end;
  WriteLn('  ---A---    ---B---    ---C---');
end;

Discussion Questions

  1. The Tower of Hanoi demonstrates that recursion depth and total work are different measures. For N = 20, the recursion depth is only 20 (trivial for the stack), but the total number of moves is 1,048,575. Why does this distinction matter for real programs?

  2. Could you use the Tower of Hanoi algorithm to actually move physical objects — say, stacking boxes of decreasing size? What real-world constraints would the algorithm ignore?

  3. The recursive solution is often described as "elegant." What makes it elegant? Is elegance a practical virtue in programming, or merely an aesthetic one?

  4. If you had to explain the Tower of Hanoi solution to someone who does not know what recursion is, how would you do it? (This exercise forces you to separate the recursive insight from the recursive mechanism.)

Key Takeaways

  • The Tower of Hanoi is the canonical example of a problem that is naturally recursive and painfully iterative.
  • The recursive solution has three lines of logic: two recursive calls and one direct move.
  • The number of moves grows exponentially (2ᴺ − 1), but the recursion depth grows only linearly (N).
  • The elegance of the recursive solution comes from trusting that the recursive calls on N − 1 work correctly — the "recursive leap of faith."