Recursion & the Call Stack — Algorithms & DS

Students often think recursion is a special language feature. It isn't. Every recursive call is an ordinary function call — which means a stack frame gets pushed, parameters get copied, a return address gets saved, and the frame gets popped on return. The only thing that makes recursion different is that the callee happens to be the same function as the caller. That's it.

What lives in a stack frame

When factorial(4) calls factorial(3), the CPU pushes a frame for the new call. That frame contains:

The return address — where to jump when this call returns
The saved frame pointer — so the caller's frame can be restored
Parameters — a copy of the argument n
Local variables — anything declared inside the function

On x86-64 Linux (the System V ABI), the first six integer arguments go in registers (rdi, rsi, …). Only if there are more than six, or if the compiler needs to spill them, do they land on the stack. A simple function like factorial may have a very small frame — but it still has one. Four levels of factorial means four live frames on the stack simultaneously.

c

int factorial(int n) {
    if (n <= 1) return 1;        // base case
    return n * factorial(n - 1);  // recursive case
}

// call stack when factorial(4) is mid-execution:
// ┌─────────────────────┐  ← stack grows downward
// │ factorial(4)  n=4   │  waiting for factorial(3)
// │ factorial(3)  n=3   │  waiting for factorial(2)
// │ factorial(2)  n=2   │  waiting for factorial(1)
// │ factorial(1)  n=1   │  base case — returns 1 now
// └─────────────────────┘
          

Notice the multiplication n * factorial(n-1) cannot execute until factorial(n-1) returns. The frame for factorial(4) must stay alive — holding its own n and its own return address — while all three inner calls run. The stack depth equals the recursion depth.

Linear vs tree recursion

Factorial is linear recursion: each call makes exactly one recursive call. The stack depth is O(n) and the total work is O(n). Naive Fibonacci is tree recursion: each call makes two recursive calls.

c

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

// fib(5) call tree (each node = one function call):
//          fib(5)
//         /      \
//      fib(4)   fib(3)
//      /    \   /    \
//   fib(3) fib(2) fib(2) fib(1)
//   ...  (fib(2) computed 3 times, fib(1) computed 5 times)
          

The call tree has O(2ⁿ) nodes. fib(50) makes over a trillion calls. Stack depth stays at O(n) — only the deepest branch is live at any moment — but the total work is exponential. This is not a recursion problem; it's a redundant computation problem. Fix it with memoization or by rewriting iteratively.

⚠️

Stack overflow is a security risk. On Linux a stack overflow usually delivers SIGSEGV, but the behavior is undefined — the overflowing writes may corrupt adjacent memory before the signal arrives. Never recurse to unbounded depth on untrusted input without a depth limit.

Tail recursion

A function is tail-recursive when the recursive call is the very last operation — there's nothing left to do after it returns. The current frame can be reused instead of keeping it alive, turning the recursion into a loop at the machine level.

c

// NOT tail-recursive — must multiply after the call returns
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // n* happens after return
}

// Tail-recursive — accumulate in a parameter instead
int fact_tail(int n, int acc) {
    if (n <= 1) return acc;
    return fact_tail(n - 1, n * acc);  // last op is the call
}
// call as: fact_tail(10, 1)
          

💡

GCC and Clang will optimize tail calls into loops with -O2, eliminating the stack growth. But the C standard doesn't require it — you can't rely on it. If depth matters, convert to an explicit loop or use an explicit stack data structure.

Converting recursion to iteration

Any recursive function can be rewritten with an explicit stack. The iterative version avoids function-call overhead and lets you control the stack size precisely. For tree traversal or DFS, this looks like:

c

// recursive DFS
void dfs_rec(Node *n) {
    if (!n) return;
    process(n);
    dfs_rec(n->left);
    dfs_rec(n->right);
}

// iterative DFS with explicit stack — same order, O(h) stack space
void dfs_iter(Node *root) {
    Node *stk[1024]; int top = -1;
    if (root) stk[++top] = root;
    while (top >= 0) {
        Node *n = stk[top--];
        process(n);
        if (n->right) stk[++top] = n->right;  // right first so left pops first
        if (n->left)  stk[++top] = n->left;
    }
}
          

one-line takeaway

Recursion is just function calls — the call stack is the implicit data structure, and understanding its depth and cost is how you know when to recurse and when to iterate.