Recursion

Big idea

A recursive function calls itself on a smaller version of the same problem, until it reaches a case small enough to answer directly.

The idea

Factorial: 5! = 5 × 4 × 3 × 2 × 1 = 120. Notice that 5! is just 5 × 4!. And 4! is 4 × 3!… down to 1!, which is simply 1.

int factorial(int n) {
    if (n <= 1) {
        return 1;                    // base case: small enough to answer
    }
    return n * factorial(n - 1);     // recursive case: a smaller problem
}

Every recursive function needs both parts:

• Base case — stops the recursion.
• Recursive case — calls itself with something closer to the base case.

Watch the calls stack up

Each call waits for the one it made. Step through factorial(3):

Watch the stack grow and unwind

Try it

#include <stdio.h>

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

int main(void) {
    printf("%d\n", digit_sum(4096));
    return 0;
}

output
19

digit_sum(4096) = 6 + digit_sum(409) = 6 + 9 + digit_sum(40) = 6 + 9 + 0 + 4 = 19.

Common mistake

A missing or unreachable base case — the calls never stop, memory for the waiting calls runs out, and the program crashes with a stack overflow:

#include <stdio.h>

void countdown(int n) {
    if (n == 0) {
        return;
    }
    printf("%d\n", n);
    countdown(n + 1);
}

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

output
3
2
1

Think of it like

Russian dolls: open one, find a smaller one inside, keep going until the tiny solid doll. Then close them back up, one at a time, in reverse.

🕷️ Spidey-sense: Two mirrors facing each other — me in a mirror in a mirror in a mirror. Cool, but without a base case, that's how you end up lost in the Mirror Dimension.

Key terms

• Recursion — A function calling itself.
• Base case — The input answered directly, without another call.
• Call stack — The pile of calls waiting to finish.
• Stack overflow — The crash when the call stack grows too deep.