TOH problem with solution for n disks

The problem

Tower of Hanoi has three pegs (source A, auxiliary B, destination C) and n disks of different sizes stacked on A with the largest at the bottom. Move all disks to C under these rules:

1. Only one disk is moved at a time.
2. Only the top disk of a peg can be moved.
3. A larger disk may never be placed on a smaller one.

Recursive solution for n disks

To move n disks from A to C using B:

1. Move the top n-1 disks from A to B (using C as auxiliary).
2. Move the largest disk n from A to C.
3. Move the n-1 disks from B to C (using A as auxiliary).

Base case: one disk is moved directly. The same idea solves the smaller problems, so it is naturally recursive.

void toh(int n, char from, char to, char aux) {
    if (n == 1) { printf("Move disk 1 from %c to %c\n", from, to); return; }
    toh(n - 1, from, aux, to);
    printf("Move disk %d from %c to %c\n", n, from, to);
    toh(n - 1, aux, to, from);
}

Number of moves

T(1) = 1 and T(n) = 2T(n-1) + 1, which gives T(n) = 2ⁿ − 1. Time complexity is O(2ⁿ).

Example n = 3 (A to C)

Total 7 = 2³ − 1 moves (generated and checked with a program).