Recursion: Base Case, Recursion Tree, Tower of Hanoi and Fibonacci

What is recursion?

Recursion is a technique in which a function solves a problem by calling itself on a smaller instance of the same problem.

Every recursive function has two parts:

1. Base case: a small input whose answer is known directly. It stops the recursion.
2. Recursive case: the function calls itself with a smaller input that moves towards the base case.

Without a base case, the function calls itself forever until the program runs out of stack memory (stack overflow).

Example 1: factorial

n! = n × (n − 1)!, with 0! = 1.

long fact(int n) {
    if (n == 0) return 1;          /* base case */
    return n * fact(n - 1);        /* recursive case */
}

How the call stack works for fact(3):

• fact(3) waits for fact(2)
• fact(2) waits for fact(1)
• fact(1) waits for fact(0)
• fact(0) returns 1
• fact(1) returns 1 × 1 = 1
• fact(2) returns 2 × 1 = 2
• fact(3) returns 3 × 2 = 6

Each call is pushed onto the call stack and popped when it returns. Time O(n), space O(n).

Example 2: Fibonacci

fib(0) = 0, fib(1) = 1, fib(n) = fib(n − 1) + fib(n − 2).

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

The recursion tree for fib(5) recomputes fib(3) twice and fib(2) three times. The number of calls grows about as fast as 1.6ⁿ, so the time is exponential. A loop, or storing the results (memoisation), makes it O(n).

Example 3: GCD (Euclid)

gcd(a, b) = a if b = 0; otherwise gcd(b, a mod b).

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6.

Example 4: Tower of Hanoi

Move n discs from peg A to peg C using peg B. Only one disc moves at a time, and a larger disc may never sit on a smaller one.

1. Move n − 1 discs from A to B (using C).
2. Move the largest disc from A to C.
3. Move n − 1 discs from B to C (using A).

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

Moves: T(n) = 2T(n − 1) + 1 with T(1) = 1, which gives T(n) = 2ⁿ − 1. For 3 discs that is 7 moves; for 64 discs it would take hundreds of billions of years at one move per second.

Types of recursion

• Direct: a function calls itself.
• Indirect: A calls B, and B calls A.
• Tail recursion: the recursive call is the last operation (like gcd above). A compiler can turn it into a loop.
• Tree recursion: more than one recursive call per invocation (like fib).

Recursion vs iteration

Exam tip

For Tower of Hanoi, write the three steps, the C function, and the 2ⁿ − 1 result. For 3 discs, list all 7 moves: A→C, A→B, C→B, A→C, B→A, B→C, A→C.