TOH for 3 disks and recursion principle

Tower of Hanoi for 3 disks

Pegs A (source), B (auxiliary), C (destination). Three disks, 1 (smallest) to 3 (largest), are on A. Rules: move one disk at a time, take only the top disk, never place a larger disk on a smaller one. Solution = TOH(3, A, C, B), where TOH(n, from, to, aux) does: TOH(n-1, from, aux, to); move disk n from→to; TOH(n-1, aux, to, from).

Recursion tree

                    TOH(3,A,C,B)
                  [4: disk 3 A->C]
              /                      \
     TOH(2,A,B,C)                TOH(2,B,C,A)
    [2: disk 2 A->B]            [6: disk 2 B->C]
      /         \                 /         \
 (1,A,C,B)   (1,C,B,A)      (1,B,A,C)   (1,A,C,B)
 [1: A->C]   [3: C->B]      [5: B->A]   [7: A->C]

Moves are printed in in-order (left subtree, node, right subtree): 1 to 7.

Calls = 7, moves = 7 = 2³ − 1.

Basic principle of recursion

A problem is solved by expressing it in terms of a smaller instance of the same problem, plus a base case that is solved directly. Every recursive call must move closer to the base case, otherwise it never stops.

Example: factorial

• Base case: fact(0) = 1
• Recursive case: fact(n) = n × fact(n-1)

int fact(int n) { return (n == 0) ? 1 : n * fact(n - 1); }

fact(3) = 3 × fact(2) = 3 × 2 × fact(1) = 3 × 2 × 1 × fact(0) = 6. The calls are stored on the stack and are resolved in reverse order when the base case returns.