Recursion

A recursive function calls itself to solve a smaller version of the same problem. Some problems — tree structures, divide-and-conquer algorithms, nested data — are far easier to express this way. In C you also need to know its cost: every call uses stack space.

The two ingredients

Every recursive function needs a base case that stops the recursion, and a recursive case that moves toward it:

#include <stdio.h>

unsigned long long factorial(unsigned n) {
    if (n <= 1) {
        return 1;                       // base case
    }
    return n * factorial(n - 1);        // recursive case
}

int main(void) {
    for (unsigned n = 0; n <= 20; n += 5) {
        printf("%2u! = %llu\n", n, factorial(n));
    }
    return 0;
}

Output

 0! = 1
 5! = 120
10! = 3628800
15! = 1307674368000
20! = 2432902008176640000

factorial(4) calls factorial(3), which calls factorial(2), down to factorial(1); then the results are multiplied on the way back up. (20! is the largest factorial that fits in 64 bits.)

Watching the calls

#include <stdio.h>

void countdown(int n, int depth) {
    printf("%*scountdown(%d)\n", depth * 2, "", n);
    if (n == 0) {
        printf("%*sbase case!\n", depth * 2 + 2, "");
        return;
    }
    countdown(n - 1, depth + 1);
    printf("%*sback in countdown(%d)\n", depth * 2, "", n);
}

int main(void) {
    countdown(3, 0);
    return 0;
}

Output

countdown(3)
  countdown(2)
    countdown(1)
      countdown(0)
        base case!
    back in countdown(1)
  back in countdown(2)
back in countdown(3)

Each call has its own copy of n, stored in its own stack frame. Code after the recursive call runs as the calls return, in reverse order.

Divide and conquer: binary search

#include <stdio.h>

int find(const int sorted[], int low, int high, int target) {
    if (low > high) return -1;                 // empty range: not found
    int mid = low + (high - low) / 2;
    if (sorted[mid] == target) return mid;
    if (sorted[mid] < target) return find(sorted, mid + 1, high, target);
    return find(sorted, low, mid - 1, target);
}

int main(void) {
    int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
    printf("%d %d\n", find(primes, 0, 10, 19), find(primes, 0, 10, 20));
    return 0;
}

Output

7 -1

Each call halves the range, so even a million elements need only about 20 calls. (low + (high - low) / 2 avoids overflow that (low + high) / 2 could cause with huge indexes.)

Recursion that does too much work

The textbook Fibonacci definition calls itself twice per step, recomputing the same values over and over:

#include <stdio.h>

static long calls = 0;

long fib(int n) {
    calls++;
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

long fib_loop(int n) {
    long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        long next = a + b;
        a = b;
        b = next;
    }
    return a;
}

int main(void) {
    printf("fib(30) = %ld using %ld calls\n", fib(30), calls);
    printf("fib(90) = %ld with a simple loop\n", fib_loop(90));
    return 0;
}

Output

fib(30) = 832040 using 2692537 calls
fib(90) = 2880067194370816120 with a simple loop

The recursive version's work grows exponentially; the loop is instant. Recursion is a tool, not always the best one.

Stack depth

Each call uses some stack memory, and the stack is limited (often 1–8 MB). Recursion thousands of levels deep, or infinite recursion from a missing base case, causes a stack overflow and the program crashes. For long linear processes — walking a long list, counting to a million — use a loop. Recursion shines when the depth stays small, as with balanced trees or binary search.

Mutual recursion

Two functions can call each other. A prototype lets the first one call the second before it's defined:

#include <stdio.h>
#include <stdbool.h>

bool is_odd(unsigned n);

bool is_even(unsigned n) { return n == 0 ? true : is_odd(n - 1); }
bool is_odd(unsigned n)  { return n == 0 ? false : is_even(n - 1); }

int main(void) {
    printf("%d %d\n", is_even(10), is_odd(7));
    return 0;
}

Output

1 1

Try it yourself

Solve the Towers of Hanoi: move n discs from peg A to peg C using B, never placing a larger disc on a smaller one.

Output

move disc 1 from A to C
move disc 2 from A to B
move disc 1 from C to B
move disc 3 from A to C
move disc 1 from B to A
move disc 2 from B to C
move disc 1 from A to C

PreviousScope & Storage NextMath Functions