Recursion in C — When It Overflows the Stack and How to Fix It

Recursion is elegant. It is also the easiest way to crash your program with a stack overflow — silently, with no error message, just a SIGSEGV. Understanding exactly how recursive calls use the stack tells you when recursion is safe and when you need to switch to an iterative approach.

How the Stack Works with Recursion

#include <stdio.h>

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

Each call to factorial pushes a new stack frame. A stack frame typically contains the return address, saved registers, and local variables. On a 64-bit Linux system, each frame for this function is around 32–64 bytes. The default stack size is 8 MB — so the maximum recursion depth before overflow is roughly 8,000,000 / 64 ≈ 125,000 levels.

#include <stdio.h>

int depth = 0;

void measure_depth(void) {
    depth++;
    measure_depth();   /* recurse until stack overflow */
}

int main() {
    measure_depth();   /* crashes, then... */
    printf("Max depth: %dn", depth);   /* never reached */
    return 0;
}

Run this (at your own risk) and the number printed just before the crash tells you your platform’s approximate maximum recursion depth. It varies by compiler flags, OS, and how much stack each frame uses.

Tail Recursion — The Optimizer’s Exception

#include <stdio.h>

/* NOT tail-recursive: must multiply n by the result after the call */
int factorial_naive(int n) {
    if (n <= 1) return 1;
    return n * factorial_naive(n - 1);   /* pending multiply — stack frame kept */
}

/* Tail-recursive: the recursive call is the last operation */
int factorial_tail(int n, int acc) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);   /* no pending work — frame can be reused */
}

int main() {
    printf("%dn", factorial_tail(10, 1));   /* 3628800 */
    return 0;
}

A tail-recursive call is one where the recursive call is the absolute last operation — no computation happens after it returns. GCC can convert this to a loop (tail-call optimization, enabled at -O2), eliminating stack growth entirely. Check with gcc -O2 -S to see the assembly — if TCO happened, you’ll see a jmp instead of a call.

Converting Recursion to Iteration

/* Recursive tree traversal */
void traverse_recursive(Node *node) {
    if (node == NULL) return;
    process(node->value);
    traverse_recursive(node->left);
    traverse_recursive(node->right);
}

/* Iterative equivalent using an explicit stack */
#include <stdlib.h>
#define MAX_STACK 1024

void traverse_iterative(Node *root) {
    Node *stack[MAX_STACK];
    int   top = 0;

    if (root) stack[top++] = root;

    while (top > 0) {
        Node *node = stack[--top];
        process(node->value);

        if (node->right) stack[top++] = node->right;
        if (node->left)  stack[top++] = node->left;
    }
}

Any recursive algorithm can be converted to an iterative one by managing your own stack on the heap. The heap is much larger than the call stack — typically limited only by available memory. This is the standard fix for deep recursion on large trees or graphs.

Memoization — When Recursion Repeats Work

#include <stdio.h>
#include <string.h>

#define MAX 100
long long memo[MAX];

long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
}

int main() {
    memset(memo, -1, sizeof(memo));
    printf("%lldn", fib(50));   /* 12586269025 */
    return 0;
}

Naive Fibonacci is O(2^n) because it recomputes every subproblem. Memoization caches results and reduces it to O(n). This is faster than the iterative version at the cost of O(n) extra memory — and still risks stack overflow for very large n. The iterative version is O(1) memory and O(n) time.

When to Use Recursion vs. Iteration

Adding a Depth Guard

#include <stdio.h>

#define MAX_DEPTH 1000

int parse(const char *input, int depth) {
    if (depth > MAX_DEPTH) {
        fprintf(stderr, "Error: input too deeply nestedn");
        return -1;
    }
    /* ... recursive parsing logic ... */
    return 0;
}

When you must use recursion and the depth is bounded by external input (like a user’s file), add an explicit depth counter and return an error when it exceeds a safe limit. User-supplied data should never drive unbounded recursion — this is an attack vector (stack exhaustion DoS).

See our guide on stack vs heap memory in C for the full picture of how call frames use the stack and why deep recursion exhausts it. Test short recursive functions in our c compiler before scaling them up.

TL;DR

• Each recursive call uses stack space — deep recursion causes stack overflow (SIGSEGV)
• Default stack depth on Linux is ~8 MB — roughly 100,000 simple frames
• Tail-recursive functions can be optimized to loops by GCC at -O2
• Convert deep recursion to an iterative loop with an explicit heap-allocated stack
• Use memoization to avoid redundant recursive calls in dynamic programming problems
• Always bound recursion driven by external input — unlimited recursion is a denial-of-service vulnerability
• Recursion is fine for O(log n) depth (binary search, balanced tree traversal); risky for O(n) depth