Stack and recursion

When a function calls another function (including itself), the runtime uses a region of memory called the call stack. Each active call gets a stack frame that is pushed when the call starts and popped when the call returns. Recursion is simply a chain of such frames for the same function name, each with its own copy of parameters and local variables. The stack is LIFO: the call that started last must finish before the one below it can resume—exactly the “unwind” you see when a base case returns.

1) What the call stack stores

Each stack frame (activation record) typically holds enough information for one invocation of a function, for example:

You do not manage this stack by hand in normal C code—the CPU and compiler do. Conceptually, though, it behaves like the abstract stacks you implement with arrays or lists: call ≈ push, return ≈ pop.

2) How recursion uses the stack

Recursive functions have a base case (stop recursing) and a recursive case (call itself with simpler input).

• Each time the recursive case runs, a new frame is pushed for the same function with a new parameter (e.g. smaller n).
• When the base case runs, it returns immediately; that frame is popped and control returns to the caller, which may multiply or combine results and then return in turn.
• The maximum depth of the call stack equals the longest chain of unfinished calls—often the recursion depth.

If recursion is too deep for the fixed call-stack size, the program can crash with stack overflow. That is why some algorithms are rewritten iteratively with an explicit stack in the heap, or converted to a loop when possible.

3) Example: factorial in C

Mathematically n! = n × (n−1) × … × 1, with 0! = 1. The recursive definition is n! = n × (n−1)! for n > 0. Each call to fact(n) waits for fact(n-1) to return—so each waiting call occupies a frame on the call stack.

#include <stdio.h>

/* Each call pushes a frame with its own n until n <= 1. */
long long fact(int n) {
    if (n <= 1)
        return 1;
    return (long long)n * fact(n - 1);
}

int main(void) {
    int n = 4;
    printf("%d! = %lld\n", n, fact(n));
    return 0;
}

For large n, recursion depth grows linearly with n; use an iterative loop or a wider type if values overflow long long. Compilers may optimize some recursions (e.g. tail recursion) only in specific cases.

Call-stack picture for fact(4)

Frames are listed bottom → top (top is the most recently entered call). When a row says “return”, that frame is popped and the value is passed back to the caller.

The last call to start (fact(1)) is the first to finish—classic LIFO stack behavior.

Key points

4) Trade-offs

• Pros — Recursive code can match mathematical definitions closely; the call stack handles saving state automatically.
• Cons — Stack space per frame; risk of overflow; sometimes slower than a tight loop due to call overhead.

Background on the abstract stack ADT: Stack introduction · Stack using array.

5) What the stack does here

Every time fact(n) is called, the system:

• Creates a stack frame (activation record).
• Stores in that frame, among other things:
  • The value of n for this call.
  • The return address (where to resume after this call returns).
  • Room for the partial computation—e.g. each caller is waiting to finish n × (result of fact(n−1)).

This follows LIFO (Last In, First Out): the most recently called function returns first.

Step-by-step execution (n = 4)

Function calls (PUSH operations)

fact(4)
 → fact(3)
   → fact(2)
     → fact(1)

At this point, the call stack looks like (top = most recent):

TOP
fact(1)
fact(2)
fact(3)
fact(4)
BOTTOM

Each call is waiting for the result of the next (inner) call.

Returning phase (POP operations)

Now execution reverses:

• fact(1) returns 1
• fact(2) → 2 × 1 = 2
• fact(3) → 3 × 2 = 6
• fact(4) → 4 × 6 = 24

The stack shrinks as each frame is discarded:

• POP fact(1)
• POP fact(2)
• POP fact(3)
• POP fact(4)

After fact(1) returns, the active chain is main → fact(4) → fact(3) → fact(2); each return removes one frame until fact(4) finally returns to main.

Visualization

During calls (stack growing)

| fact(4) |
| fact(3) |
| fact(2) |
| fact(1) | ← Top

During returns (stack shrinking)

| fact(4) | ← Last among recursive calls to finish (then returns to main)

Earlier in the unwind, more frames are still present (e.g. right after fact(1) returns, the top frame is fact(2)); the diagram above highlights that fact(4) is the outermost recursive frame and completes last.