Recursion in C: Base Cases, Factorial, and Stack Depth

A Function That Calls Itself

Nothing stops a C function from calling itself. Its own name is in scope inside its body, so this is legal:

void countdown(int n) {
    printf("%d\n", n);
    countdown(n - 1);      /* calls itself - but never stops! */
}

It is also broken. It prints forever, into negative numbers, until the program crashes. What it is missing is a base case: a condition under which the function returns without calling itself.

#include <stdio.h>

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

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

Every recursive function has exactly these two parts:

• A base case - the smallest input, answered directly, with no further call.
• A recursive case - solves the problem in terms of a strictly smaller version of itself.

"Strictly smaller" is the part people get wrong. countdown(n - 1) moves toward 0 on every call. countdown(n) would not, and neither would countdown(n / 2) if n could be 1 forever. Every path must shrink the problem, or the base case is never reached.

Factorial

The standard first example. n! is n × (n-1) × ... × 1, and 0! is defined as 1. That definition is already recursive: n! = n × (n-1)!.

#include <stdio.h>

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

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

Trace factorial(4) to see how the answer is assembled. The calls go down, and the multiplications happen on the way back up:

factorial(4)  -> 4 * factorial(3)
                      factorial(3) -> 3 * factorial(2)
                                           factorial(2) -> 2 * factorial(1)
                                                                factorial(1) -> 1   (base case)
                                           factorial(2) = 2 * 1  = 2
                      factorial(3) = 3 * 2  = 6
factorial(4)  = 4 * 6  = 24

Nothing is multiplied until the base case returns. Every pending call sits waiting, holding its own n, which is the point worth internalising: those waiting calls occupy memory.

Note the return type. int overflows around 13!, silently producing a wrong number - C does not check. unsigned long long gets you to 20! and no further, because 21! exceeds 64 bits. Recursion is not the limiting factor here; the type is.

The base case uses n <= 1 rather than n == 1 deliberately: factorial(0) should be 1, and <= handles it. With n == 1, calling factorial(0) would recurse to -1, -2, and never terminate - a good illustration of how an "obviously correct" base case can miss an input.

Fibonacci, and Why the Naive Version Is a Trap

Fibonacci is the other classic: each number is the sum of the two before it, starting from 0 and 1. The recursive definition writes itself.

#include <stdio.h>

long long calls = 0;

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

int main(void) {
    for (int n = 10; n <= 35; n += 5) {
        calls = 0;
        int result = fib(n);
        printf("fib(%2d) = %-8d (%lld calls)\n", n, result, calls);
    }
    return 0;
}

Look at the call counts. fib(10) takes 177 calls; fib(35) takes nearly 30 million. Each step of 5 multiplies the work by about eleven.

The reason is visible in the call tree. fib(5) calls fib(4) and fib(3); fib(4) calls fib(3) again; and each of those recomputes fib(2) from scratch. Nothing is remembered, so the same subproblems are solved over and over, and the number of calls grows roughly like 1.6ⁿ. fib(50) this way would run for days; fib(100) would outlast the universe.

The loop version keeps the last two values and is linear:

#include <stdio.h>

long long fibFast(int n) {
    if (n < 2) {
        return n;
    }
    long long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    for (int n = 10; n <= 90; n += 10) {
        printf("fib(%2d) = %lld\n", n, fibFast(n));
    }
    return 0;
}

fib(90) returns instantly. The lesson is not "recursion is slow" - it is that recursion with overlapping subproblems is slow unless you remember the answers. Store results in an array as you compute them (memoization) and the recursive version becomes linear too.

The Call Stack and Stack Overflow

Every function call needs somewhere to keep its parameters, its locals, and the address to return to. That storage is a stack frame, pushed when the call starts and popped when it returns. Recursion stacks frames one on top of another - factorial(1000) has a thousand frames live at once, each with its own n.

The stack is not large. A typical default is 1-8 MB, so a few tens of thousands of frames is the realistic limit, and much less if each frame holds a big local array. Exceed it and the program dies:

Segmentation fault (core dumped)

That is a stack overflow, and there are two ways to get one:

Infinite recursion - a missing or unreachable base case. This is a bug, and the crash is immediate:

int bad(int n) {
    return bad(n - 1);      /* no base case - crashes in a fraction of a second */
}

Correct but too deep - recursing once per element over a million-item list. The logic is right; the approach does not fit in the stack. Rewrite it as a loop, or restructure so the depth is logarithmic (recursing on halves, as binary search and merge sort do, gives a depth of about 20 for a million items).

Some compilers can turn tail recursion - where the recursive call is the very last thing the function does, with no pending work after it - into a loop, reusing one frame. countdown above is tail recursive; factorial is not, because the multiplication still has to happen after the call returns. But C does not require this optimisation, so it may or may not happen depending on the compiler and the flags. Never write C that only works because the optimiser eliminated a tail call.

Where Recursion Genuinely Wins

Every recursive function can be rewritten as a loop, and for simple counting the loop is plainly better. Recursion earns its keep when the data itself is recursive - when a structure contains smaller copies of itself.

Binary search is a clean example: search half, then half of that.

#include <stdio.h>

/* returns the index of target, or -1 */
int binarySearch(const int a[], int low, int high, int target) {
    if (low > high) {
        return -1;                          /* base case: nothing left */
    }
    int mid = low + (high - low) / 2;       /* avoids overflow on big indices */

    if (a[mid] == target) {
        return mid;                         /* base case: found it */
    }
    if (a[mid] < target) {
        return binarySearch(a, mid + 1, high, target);
    }
    return binarySearch(a, low, mid - 1, target);
}

int main(void) {
    int sorted[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(sorted) / sizeof(sorted[0]);

    int targets[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) {
        printf("%2d -> index %d\n", targets[i], binarySearch(sorted, 0, n - 1, targets[i]));
    }
    return 0;
}

Two base cases here, which is normal: one for success and one for exhaustion. The depth is about log₂(n), so even a billion elements need only thirty frames.

Other places recursion is the natural fit: walking a tree or a linked list, directory traversal, parsing nested expressions, and divide-and-conquer sorts like quicksort and merge sort. In all of them the recursive code is shorter and clearer than the loop with an explicit stack that replaces it.

Recursion or a Loop?

Use a loop when       the problem is linear - counting, summing, scanning
Use recursion when    the data is nested - trees, nested structures, divide and conquer
Rewrite recursion     if the depth can grow with the input size without bound
Never use recursion   when subproblems overlap, unless you memoize

Two practical notes. Recursive calls cost a little more than a loop iteration - a frame to push and pop each time - so for hot, simple loops the iterative version wins on speed as well as memory. And debugging is different: a stack trace from deep recursion is hundreds of identical-looking frames, so print the parameter at entry (as the calls counter above does) when something is not terminating.

Writing a Recursive Function: A Checklist

1. Find the base case first. What is the smallest input, and what is its answer? If you cannot name it, the function cannot be written.
2. Assume the recursive call works. Do not trace it through mentally - trust factorial(n - 1) to return (n-1)! and write the one step that turns it into the answer.
3. Check every path shrinks. Each recursive call must move toward the base case for every possible input, including 0 and negatives.
4. Check the depth. Roughly how many frames deep will this go on real data? Thousands is fine; millions is not.
5. Check for overlap. If the same subproblem is computed twice, you need memoization or a loop.