Tree recursion and TOH with n disks

Tree recursion

A recursive function that makes more than one recursive call in its body is tree recursive, because the calls form a tree. Examples: Fibonacci fib(n-1) + fib(n-2) and Tower of Hanoi (two calls for n-1 disks). Linear recursion (one call, like factorial) forms a chain instead.

Algorithm TOH(n, from, to, aux)

1. If n = 1: move disk 1 from from to to; return.
2. TOH(n-1, from, aux, to).
3. Move disk n from from to to.
4. TOH(n-1, aux, to, from).

#include <stdio.h>

/* move n disks from 'from' to 'to' using 'aux' */
void toh(int n, char from, char to, char aux) {
    if (n == 1) {                                   /* base case */
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    toh(n - 1, from, aux, to);                      /* step 1 */
    printf("Move disk %d from %c to %c\n", n, from, to);   /* step 2 */
    toh(n - 1, aux, to, from);                      /* step 3 */
}

int main(void) {
    toh(3, 'A', 'C', 'B');
    return 0;
}

Recursion tree for 3 disks, call TOH(3, A, C, B)

                    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.

Move sequence (verified by running the algorithm):

Calls = 2³ − 1 = 7, tree depth = 3, moves = 7.