C Recursion

A recursive function is a function that calls itself. Some problems are naturally described in terms of a smaller version of themselves, and recursion lets the code follow that description directly.

Factorial

The factorial of n, written n!, is n × (n−1) × … × 1. It can be described recursively: n! = n × (n−1)!, and 1! = 1.

#include <stdio.h>

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

int main(void) {
    printf("5! = %ld\n", factorial(5));
    printf("10! = %ld\n", factorial(10));
    return 0;
}

5! = 120
10! = 3628800

Every recursive function needs two parts:

• a base case that returns a value directly, without another call;
• a recursive case that calls the function on a smaller problem, getting closer to the base case each time.

How the calls unfold

factorial(4) calls factorial(3), which calls factorial(2), which calls factorial(1). That one returns 1; then each waiting call finishes: 2 × 1 = 2, 3 × 2 = 6, 4 × 6 = 24. Each call has its own n, kept on the call stack until it finishes.

Sum of digits

#include <stdio.h>

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

int main(void) {
    printf("digitSum(2026) = %d\n", digitSum(2026));
    return 0;
}

digitSum(2026) = 10

Fibonacci

Each Fibonacci number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, …

#include <stdio.h>

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

int main(void) {
    for (int i = 0; i < 10; i++) {
        printf("%d ", fib(i));
    }
    printf("\n");
    return 0;
}

0 1 1 2 3 5 8 13 21 34 

This version is short but slow for large n, because it computes the same values again and again. A loop that keeps the last two numbers is much faster. Recursion is elegant; it is not always the best tool.

When recursion never stops

Without a base case, or with one that is never reached, the function calls itself until the call stack is full and the program stops with a stack overflow. In the editor the terminal says the recursion went too deep. Try it: remove the base case from factorial and run it.

Practice exercises

1. Write a recursive function that computes the power base to the exp.
2. Write a recursive function that prints a string backwards.
3. Rewrite factorial with a loop and compare the results for 1 to 10.
4. Write a recursive function for the greatest common divisor: gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a.