Recursion: Functions That Call Themselves

A function can call itself. This is called recursion. It sounds strange, but it is a neat way to solve problems that contain smaller copies of themselves.

Think of it like this: Russian dolls: to find the smallest doll, open a doll. If there's another doll inside, do the same thing again. When a doll doesn't open, you're done.

#include <stdio.h>

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

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

Output

3
2
1
Go!

Every recursive function needs two parts:

• A base case: when to stop (here: n == 0).
• A recursive step: call itself with a smaller problem (here: n - 1).

Factorial

The factorial of 5 (written 5!) is 5 × 4 × 3 × 2 × 1 = 120. Notice that 5! = 5 × 4!, and 4! = 4 × 3!, and so on:

#include <stdio.h>

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

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

Output

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720

Common mistake: Forgetting the base case. The function then calls itself forever, until the computer runs out of memory and the program crashes.

Tip: Anything you can do with recursion, you can also do with a loop. Use whichever is easier to read.