Step 6 of 7

Recursion

A function can call itself. This is called recursion, and it's a natural fit for problems defined in terms of smaller versions of themselves.

Take factorial: 5! = 5 x 4 x 3 x 2 x 1. Notice that 5! is just 5 x 4!, and 4! is 4 x 3!, and so on down to 1! = 1. That translates directly into code:

#include <stdio.h>

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

int main(void) {
    printf("%d %d %d\n", factorial(1), factorial(5), factorial(10));
    return 0;
}

1 120 3628800

The two parts every recursive function needs

1. A base case that answers directly, without recursing (n <= 1 returns 1).
2. A recursive case that calls itself on a smaller problem (n - 1), so it eventually reaches the base case.

How it runs

Each call gets its own copy of n, stored in its own stack frame. factorial(3) calls factorial(2), which calls factorial(1). Now three calls are paused, waiting. factorial(1) returns 1, then factorial(2) finishes with 2 x 1 = 2, then factorial(3) finishes with 3 x 2 = 6. The calls stack up, then unwind. Use the Watch it run link below to see the frames appear and disappear.

Without a base case (or if the problem never gets smaller), the calls pile up until the program runs out of stack memory and crashes with a stack overflow.

Fibonacci

For this step, each Fibonacci number depends on the two before it, so the recursive case makes two calls. You need two base cases (0 and 1). This simple version recomputes the same values many times, so it's slow for large n; that's fine here, and you'll learn faster techniques later.

Your turn: write int fib(int n) returning the n-th Fibonacci number, where fib(0) = 0, fib(1) = 1 and every later number is the sum of the two before it.

Previous: Scope and pass by value Next: Challenge: is it prime?