Recursion in C

Some problems contain smaller copies of themselves. Recursion in C is a technique where a function solves a problem by calling itself on a smaller piece of it, until the piece is so small the answer is obvious. In this lesson, you'll write recursive functions for countdowns, factorials, digit sums and Fibonacci numbers, see how the call stack grows and shrinks, and learn when a plain loop is the better choice.

What is recursion in C?

A recursive function is a function that calls itself. Every working recursive function has two parts:

• Base case: the simplest input, answered directly without another call. This is what stops the recursion.
• Recursive case: the function calls itself with a smaller input, moving one step closer to the base case.

Here's a rocket countdown. The base case is n == 0; the recursive case prints n and counts down from n - 1.

#include <stdio.h>

void countdown(int n) {
    if (n == 0) {                 /* base case */
        printf("Liftoff!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);             /* recursive case */
}

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

3
2
1
Liftoff!

Factorial: the classic recursion example

The factorial of n (written n!) is n × (n-1) × ... × 1. For example, 4! = 4 × 3 × 2 × 1 = 24. Notice that 4! = 4 × 3!. A factorial contains a smaller factorial, which makes it a natural fit for recursion:

#include <stdio.h>

int factorial(int n) {
    if (n <= 1) {
        return 1;                     /* base case: 0! and 1! are 1 */
    }
    return n * factorial(n - 1);      /* recursive case */
}

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

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

How does recursion work? The call stack

Every time a function is called, C sets aside a small chunk of memory called a stack frame. It holds that call's parameters and local variables (remember from variable scope that each call gets its own fresh locals). Frames are piled up on the call stack: a new call goes on top, and when a call returns, its frame is removed.

So factorial(3) can't finish until factorial(2) gives it an answer, and factorial(2) waits for factorial(1). The stack grows until the base case, then shrinks as each waiting call multiplies and returns.

You can watch this happen by adding a few printf calls:

#include <stdio.h>

int factorial(int n) {
    printf("Calling factorial(%d)\n", n);
    if (n <= 1) {
        printf("Base case reached, returning 1\n");
        return 1;
    }
    int result = n * factorial(n - 1);
    printf("factorial(%d) returns %d\n", n, result);
    return result;
}

int main(void) {
    printf("Answer: %d\n", factorial(3));
    return 0;
}

Calling factorial(3)
Calling factorial(2)
Calling factorial(1)
Base case reached, returning 1
factorial(2) returns 2
factorial(3) returns 6
Answer: 6

The "Calling" lines appear on the way down, and the "returns" lines appear in reverse order on the way back up. Answer: 6 is printed last because printf needs the finished result before it can print anything.

Sum of digits with recursion

Recursion is handy whenever you can peel off one piece and repeat. To add the digits of a number, take the last digit with n % 10, and add the digit sum of the rest, n / 10. A single-digit number is the base case.

#include <stdio.h>

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

int main(void) {
    printf("Sum of digits of 4096 is %d\n", sum_digits(4096));
    return 0;
}

Sum of digits of 4096 is 19

The calls go 4096 → 409 → 40 → 4, then add up on the way back: 4 + 0 + 9 + 6 = 19.

Fibonacci: why the simple version is slow

In the Fibonacci sequence, each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, ... The definition is recursive, so the code looks almost exactly like the math:

#include <stdio.h>

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

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

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

It's correct, but it does a huge amount of repeated work. fib(5) calls fib(4) and fib(3), but fib(4) also calls fib(3), and so on. The number of calls roughly doubles each time n grows. Let's count them with a global counter:

#include <stdio.h>

int calls = 0;

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

int main(void) {
    int answer = fib(20);
    printf("fib(20) = %d\n", answer);
    printf("Function calls: %d\n", calls);
    return 0;
}

fib(20) = 6765
Function calls: 21891

Almost 22,000 calls for one small answer! fib(40) would need over 300 million. A loop that remembers just the last two numbers needs only 40 steps:

#include <stdio.h>

int fib_loop(int n) {
    int a = 0;
    int b = 1;
    for (int i = 0; i < n; i++) {
        int next = a + b;
        a = b;
        b = next;
    }
    return a;
}

int main(void) {
    printf("fib(20) = %d\n", fib_loop(20));
    printf("fib(40) = %d\n", fib_loop(40));
    return 0;
}

fib(20) = 6765
fib(40) = 102334155

What happens without a base case? Stack overflow

If a recursive function never reaches a base case, it keeps calling itself, and every call adds another frame to the call stack.

void forever(int n) {
    forever(n + 1);   /* no base case: never stops */
}

The call stack is small (often around 1 to 8 MB). After many thousands of calls it runs out of room. This is called a stack overflow, and the program crashes, usually with a message like Segmentation fault on Linux and macOS, or simply exits with an error code on Windows. The same happens if the recursive case doesn't move toward the base case, for example calling countdown(n + 1) instead of countdown(n - 1).

Recursion vs loops: which should you use?

Anything you can do with recursion, you can also do with a loop, and vice versa. Choose the one that makes the code clearer and safe.

Common mistakes

1. Forgetting the base case

Without a base case, the function calls itself until the stack overflows and the program crashes. Write the base case first, before the recursive call.

2. Not making the problem smaller

return n * factorial(n); calls itself with the same value forever. Each call must move toward the base case: factorial(n - 1).

3. A base case that can be skipped

With if (n == 1) as the only base case, calling factorial(0) goes to -1, -2, ... and never stops. Using n <= 1 catches 0 and negative numbers too.

4. Forgetting to return the recursive result

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    n * factorial(n - 1);   /* result thrown away: no return */
}

GCC warns that control reaches the end of a non-void function, and the caller gets a garbage value. Always write return in front of the recursive expression.

Practice exercise

#include <stdio.h>

int power(int base, int exponent) {
    if (exponent == 0) {
        return 1;
    }
    return base * power(base, exponent - 1);
}

int main(void) {
    printf("2^10 = %d\n", power(2, 10));
    printf("3^4 = %d\n", power(3, 4));
    printf("5^0 = %d\n", power(5, 0));
    return 0;
}

2^10 = 1024
3^4 = 81
5^0 = 1

What's next?

You've written functions that call other functions and even themselves. To finish the chapter, meet the ready-made functions C gives you for square roots, powers and rounding: C math functions.