Recursion in C

Recursion in C is when a function calls itself to solve a smaller version of the same problem, until it reaches a simple case it can answer directly. Every recursive function needs two parts: a base case that stops the recursion, and a recursive case that moves toward that base case.

The two essential parts

Think of recursion as breaking a problem into a smaller copy of itself:

• Base case — the simplest input, answered without recursion. This stops the chain.
• Recursive case — the function calls itself with a smaller input.

Without a base case, the function calls itself forever and crashes (a stack overflow).

Factorial: the classic example

The factorial of n (written n!) is n × (n-1) × ... × 1. Notice that n! = n × (n-1)!, which is naturally recursive:

#include <stdio.h>

/* factorial(n) = n * factorial(n-1), with factorial(0) = 1 */
long factorial(int n) {
    if (n <= 1) {           /* BASE CASE: stops the recursion */
        return 1;
    }
    return n * factorial(n - 1);   /* RECURSIVE CASE: smaller problem */
}

int main(void) {
    printf("5! = %ld\n", factorial(5));   /* 120 */
    return 0;
}

To compute factorial(5), C computes 5 * factorial(4), which needs 4 * factorial(3), and so on down to factorial(1) returning 1. The results then multiply back up the chain.

The call stack

Each call to a function gets its own slot on the call stack, holding its own copy of the parameters. As recursion goes deeper, the stack grows; as each call returns, its slot is freed. This is why very deep recursion can exhaust the stack and crash — the depth is limited.

Fibonacci: recursion with two calls

#include <stdio.h>

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

int main(void) {
    for (int i = 0; i < 8; i++) {
        printf("%d ", fib(i));   /* 0 1 1 2 3 5 8 13 */
    }
    printf("\n");
    return 0;
}

This is elegant but slow for large n, because it recomputes the same values many times. For big inputs an iterative loop is far faster.

Recursion vs iteration

Anything you can do with recursion you can also do with a loop, and vice versa. Recursion shines when a problem is naturally recursive — tree structures, divide-and-conquer, traversals. Loops are usually faster and use less memory for simple counting tasks.

Common mistakes

• No base case (or unreachable one): the function never stops and overflows the stack.
• Recursive call that doesn't shrink the problem: e.g. calling factorial(n) instead of factorial(n - 1) — infinite recursion.
• Wrong base condition, returning the wrong starting value (factorial of 0 should be 1, not 0).
• Assuming recursion is always best — for deep or simple repetition, a loop avoids stack limits.
• Overflowing the return type: factorials grow fast; int overflows quickly, so use long or long long.

FAQ

What is a stack overflow? When recursion goes too deep, the call stack runs out of space and the program crashes. A correct base case prevents it.

Is recursion slower than loops? Often slightly, due to function-call overhead. Use it for clarity on naturally recursive problems.

Build on this at the hub C Programming, with Functions in C and For Loops in C.

Want to learn this properly? Join the waitlist for our C Programming course — taught in Jalgaon.