Box trace and TOH recursion tree

Box trace

A box trace is a manual tool for tracing recursive functions. Every call is drawn as a box holding the function's parameters, local variables, a return address (label) and the return value. When a function calls itself, a new box is drawn and linked to the caller's box by an arrow. When a call finishes, its box is crossed out and control goes back to the label in the caller's box. It shows the run-time stack of activation records.

Example for fact(3):

fact(3): n=3, returns 3*fact(2)
   fact(2): n=2, returns 2*fact(1)
      fact(1): n=1, returns 1

The innermost box returns 1, then 2 and finally 6.

Recursion tree for Tower of Hanoi (3 disks)

TOH(n, from, to, aux): move n−1 disks from→aux, move disk n from→to, move n−1 disks aux→to.

Let the pegs be A (source), C (destination), B (auxiliary).

              TOH(3,A,C,B)
            /      |       \
   TOH(2,A,B,C)  A->C   TOH(2,B,C,A)
    /    |    \            /    |    \
 T(1)  A->B  T(1)       T(1)  B->C  T(1)
A,C,B       C,B,A      B,A,C       A,C,B
  |           |           |           |
 A->C        C->B        B->A        A->C

T(1) = TOH(1, from, to, aux) is a leaf: it just moves one disk. Reading the moves from left to right gives the 7 moves (2³ − 1):

1. A→C (disk 1)
2. A→B (disk 2)
3. C→B (disk 1)
4. A→C (disk 3)
5. B→A (disk 1)
6. B→C (disk 2)
7. A→C (disk 1)

The tree has 7 calls (1 + 2 + 4), each producing exactly one move, and its height is 3. Total moves T(n) = 2T(n−1) + 1 = 2ⁿ − 1.