Recursion in C: Base Case, Recursive Case and Classic Examples

A recursive function calls itself to solve a smaller version of the same problem. Every recursive function needs two parts:

1. A base case: a simple input answered directly, which stops the recursion.
2. A recursive case: the function calls itself with an input closer to the base case.

Factorial#

n! = n × (n−1)!, and 0! = 1:

#include <stdio.h>

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

int main(void) {
    printf("%lld\n", factorial(5));
    printf("%lld\n", factorial(20));
    return 0;
}

120
2432902008176640000

factorial(5) calls factorial(4), which calls factorial(3), and so on down to factorial(1), which returns 1. The results then multiply on the way back up: 2, 6, 24, 120.

More examples#

#include <stdio.h>

int sum_digits(int n) {
    if (n < 10) return n;
    return n % 10 + sum_digits(n / 10);
}

double power(double base, int exp) {
    if (exp == 0) return 1;
    double half = power(base, exp / 2);         /* square-and-multiply: O(log n) */
    return exp % 2 == 0 ? half * half : half * half * base;
}

void print_binary(unsigned n) {
    if (n > 1) print_binary(n / 2);
    printf("%u", n % 2);
}

int main(void) {
    printf("%d\n", sum_digits(9875));
    printf("%.0f\n", power(2, 30));
    print_binary(13);
    printf("\n");
    return 0;
}

29
1073741824
1101

print_binary prints after the recursive call, so the digits come out in the right order.

The call stack#

Each call gets its own stack frame holding its parameters and local variables. Calls pile up until the base case is reached, then unwind. Every frame uses memory, so very deep recursion can exhaust the stack and crash the program (a stack overflow). The stack is typically a few megabytes, so recursion that goes a million levels deep is not practical; use a loop for that.

A recursive function without a reachable base case recurses until the stack overflows.

Fibonacci: a warning#

The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, ...) has a natural recursive definition, but the direct implementation repeats the same work exponentially many times:

#include <stdio.h>

long long calls = 0;

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

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

int main(void) {
    long long f = fib(30);      /* call first: argument order is unspecified */
    printf("fib(30) = %lld after %lld calls\n", f, calls);
    printf("fib_loop(30) = %lld\n", fib_loop(30));
    printf("fib_loop(90) = %lld\n", fib_loop(90));
    return 0;
}

fib(30) = 832040 after 2692537 calls
fib_loop(30) = 832040
fib_loop(90) = 2880067194370816120

Over 2.6 million calls for fib(30), while the loop needs 30 steps. Recursion is elegant, but check how much work it really does.

fib(30) is stored in f before the printf. C does not specify the order in which a function's arguments are evaluated, so passing fib(30) and calls as arguments of the same call could read calls before fib runs. With GCC on Windows, that version prints 0 calls.

Binary search#

Recursion fits naturally when a problem splits into halves:

#include <stdio.h>

int binary_search(const int a[], int lo, int hi, int target) {
    if (lo > hi) return -1;                 /* not found */
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == target) return mid;
    if (a[mid] < target) return binary_search(a, mid + 1, hi, target);
    return binary_search(a, lo, mid - 1, target);
}

int main(void) {
    int sorted[] = {3, 8, 15, 23, 42, 57, 91};
    printf("%d\n", binary_search(sorted, 0, 6, 42));
    printf("%d\n", binary_search(sorted, 0, 6, 10));
    return 0;
}

4
-1

lo + (hi - lo) / 2 avoids the integer overflow that (lo + hi) / 2 can cause for very large arrays.

Recursion or loops?#

Use recursion when the problem is naturally recursive: trees, divide-and-conquer algorithms (merge sort, quicksort), exploring paths. Use loops for simple repetition and for very deep processes, which avoids stack overflows and function-call overhead.

Practice#

#include <stdio.h>

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

void reverse_print(const char *s) {
    if (*s == '\0') return;
    reverse_print(s + 1);
    putchar(*s);
}

int main(void) {
    printf("%d\n", gcd(84, 36));
    reverse_print("recursion");
    printf("\n");
    return 0;
}

12
noisrucer

Key takeaway#