The Stack and Function Calls

Every time you call a function in C, the runtime pushes a stack frame that holds the function's parameters, local variables, and the return address it needs to come back to its caller. When the function returns, that frame is popped — and every local in it is gone.

This page makes that mechanism concrete enough that you can predict how recursion uses memory and where local pointers stop being safe to read.

Anatomy of a stack frame

A typical frame contains:

• the return address (where to resume in the caller)
• the saved frame pointer (so debuggers can walk the call chain)
• the function's parameters (or in many ABIs, copies of register arguments)
• the function's local variables
• on some platforms, padding to keep alignment

The stack typically grows from high addresses to low — every call subtracts from the stack pointer, every return adds back. On WASI the direction is the same conceptually even if the linear memory layout differs.

See the stack with addresses

You can see the call chain by printing addresses of local variables.

The addresses of x in main, middle, and inner should be decreasing (or sometimes increasing — the direction is platform-dependent), and the difference between consecutive frames shows roughly how big each frame is.

Recursion uses the stack

Each recursive call pushes a new frame. A function that recurses n times uses n frames at peak — so a recursion depth limit is really a stack size limit.

fib(40) would push roughly 2 × 10⁸ frames in total over its run (though only ~40 are alive at once because the calls return between them). The total work explodes; the peak stack depth is only n.

Stack overflow

When recursion is too deep — or a function declares a huge local array — you hit the end of the stack region and the program crashes with a stack overflow.

Iteration vs recursion — same algorithm, different memory shape

Many recursive algorithms have iterative equivalents that use O(1) stack instead of O(n). Compare:

Both compute the same value. The iterative version is friendlier on the stack and easier for an optimizer to reduce to a tight loop.

Tail calls

In return f(...) — where the recursive call is the very last thing the function does — a sufficiently aggressive optimizer can reuse the current frame instead of pushing a new one. This is called tail-call optimization (TCO). C compilers will sometimes perform it at higher optimization levels but the language does not guarantee it.

// Tail-recursive form of factorial: every recursive call is the function's
// last action, with the accumulated product passed as a parameter.
long fact_tail(int n, long acc) {
    if (n <= 1) return acc;
    return fact_tail(n - 1, n * acc);
}

If you depend on tail calls (e.g. for an interpreter loop), measure with -O2. Otherwise prefer an explicit loop.

Lifetimes: when a local stops being valid

The single most important stack rule:

A local variable lives only between the matching { and }. Any pointer to it becomes invalid the instant control leaves that scope.

The pattern that is safe: write into a buffer the caller owns.

This caller owns the buffer idiom is everywhere in C APIs: think fgets(buf, sizeof buf, stdin) or snprintf(buf, sizeof buf, ...).

Practice: iterative power

Practice: greatest common divisor (iterative)

Test your understanding

char *greeting(void) {
  char buf[16] = "Hello";
  return buf;
}