Recursion basics

A recursive function is one that calls itself. This is not just a neat trick — recursion is the natural way to express a large class of problems, particularly those where a large problem can be broken into smaller versions of the same problem. It is also how C function calls work at the hardware level, making it a useful mental model for understanding the call stack.

The structure of recursion

Every recursive function needs two things:

1. A base case: a condition under which the function does NOT call itself — it returns directly. Without this, recursion never terminates.
2. A recursive case: where the function calls itself with a smaller or simpler argument, moving toward the base case.

Factorial

The factorial of n (written n!) is n × (n−1) × (n−2) × ... × 1. By definition, 0! = 1.

Mathematically: n! = n × (n-1)! with base case 0! = 1.

#include <stdio.h>

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

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

Output:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040

Trace factorial(4) by hand:

• factorial(4) calls factorial(3)
• factorial(3) calls factorial(2)
• factorial(2) calls factorial(1)
• factorial(1) calls factorial(0)
• factorial(0) returns 1 (base case)
• factorial(1) returns 1 × 1 = 1
• factorial(2) returns 2 × 1 = 2
• factorial(3) returns 3 × 2 = 6
• factorial(4) returns 4 × 6 = 24

Each call is pushed onto the call stack; each return pops it off.

What happens without a base case

int broken_factorial(int n) {
    return n * broken_factorial(n - 1); /* no base case! */
}

This will eventually crash with a stack overflow — the program keeps pushing stack frames until it runs out of stack memory. The operating system terminates it with a segmentation fault. Stack space is typically limited to a few megabytes, so deep recursion can overflow even with a correct base case.

Fibonacci

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Definition: fib(0) = 0, fib(1) = 1, fib(n) = fib(n-1) + fib(n-2).

#include <stdio.h>

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

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

Recursion vs. iteration

Recursive factorial is elegant but a simple loop is faster and uses less memory:

int factorial_iter(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

No stack frames accumulate — just a single running product. For the problems in this module, the iterative version is clearly better. Recursion shines for tree traversal, divide-and-conquer algorithms, and parsing — cases where the structure of the problem is naturally recursive.

Binary search — a practical recursive example

Binary search is a natural fit for recursion:

#include <stdio.h>

int binary_search(int arr[], int low, int high, int target) {
    if (low > high) {
        return -1; /* base case: not found */
    }
    int mid = low + (high - low) / 2;
    if (arr[mid] == target) {
        return mid; /* base case: found */
    } else if (arr[mid] < target) {
        return binary_search(arr, mid + 1, high, target);
    } else {
        return binary_search(arr, low, mid - 1, target);
    }
}

int main(void) {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = 10;
    int idx = binary_search(arr, 0, n - 1, 23);
    printf("Found 23 at index %d\n", idx); /* 5 */
    return 0;
}

At each step, half the remaining search space is eliminated. The depth of recursion is at most log₂(n) — for a million elements, that is only 20 levels deep.

Where to go next

Next: the factorial and Fibonacci lab — you will implement both problems from scratch, test them, and compare the recursive and iterative versions.