Functions, calls and the stack

Functions are the main way to structure a program: a name for a piece of work that can be used without knowing how it's done. To the caller, a call looks like a single new operation. Underneath, every call has a cost and a structure. The calling conventions chapter at the assembly level shows the mechanics — call, ret, argument registers, the frame pointer. This chapter looks at what they mean for C code: where parameters and local variables live, how long they last, and what that implies.

Every call gets its own frame

When a function is called, it gets a new stack frame: a block of stack memory holding its return address, its saved frame pointer, and its local variables and parameters. When the function returns, the frame is released. The key word is every: two calls to the same function, even two active at once, get two separate frames. That's what makes recursion work — a function calling itself:

The demo opens mid-recursion, at the deepest point. The call stack shows main and five fact frames, and each frame has its own n: 5, 4, 3, 2 and 1. They're all called n, but they're five different variables at five different addresses, 32 bytes apart. Step on and the frames unwind one by one, each multiplying its own n into the result: the program returns 120.

Tanenbaum's classic example is the Towers of Hanoi: move a stack of disks from one peg to another, one disk at a time, never putting a larger disk on a smaller one. The recursive solution is three lines — move n − 1 disks out of the way, move the largest, move the n − 1 disks back on top:

It prints the 7 moves for three disks. Each active call keeps its own n, from, to and other in its frame while its sub-calls run. The book draws the stack growing upward, toward higher addresses; on x86, ARM and RISC-V it grows downward, so each new frame sits below its caller's. The idea is the same.

Parameters are copies

C passes every argument by value: the function receives a copy in its own frame. Changing the parameter changes the copy, never the caller's variable:

void reset(int n) {
    n = 0;          // changes reset's own n
}

int main() {
    int n = 5;
    reset(n);
    return n;       // still 5
}

To let a function change a caller's variable, pass its address, like the swap function in pointers and arrays. Arrays seem to be an exception, but they aren't: what gets copied is the pointer the array decays into. Structs, on the other hand, are copied whole, which is why large structs are usually passed by pointer.

Locals die when the function returns

A local variable exists only while its function's frame does. Returning its address hands the caller a pointer into memory that has already been released — a dangling pointer. The next call reuses the same stack space:

It returns 7, not 42. other's frame was built in exactly the same place as make's, and its y landed where x used to be. Compilers warn about this one — clang says address of stack memory associated with local variable 'x' returned. gcc goes further: it quietly compiles return &x; to return NULL instead, so the real program crashes with a segmentation fault rather than reading stale data. Both behaviors are allowed, because using a dead variable is undefined behavior.

The fix depends on what the value needs to outlive. Return the value itself, not its address; let the caller pass in a buffer; or allocate on the heap with malloc, which is the subject of the next chapter.

How deep can you go?

The stack is a fixed-size region reserved when a thread starts. On Linux it's 8 MiB by default for the main thread (ulimit -s prints 8192, in KiB), on Windows 1 MiB. Each call uses a frame's worth of it, so a recursion that goes too deep — or never stops — runs out. Beyond the stack's limit, the OS leaves a guard region that's never mapped: touching it faults, and the process dies with a segmentation fault. That's a stack overflow.

This function's frame holds a 4,000-byte array, so it eats the stack quickly. Press Continue to run it to the end:

The simulator's stack is 1 MiB, and it overflows at a depth of 261: the call stack ends with dive(n=261), above 260 other dive frames. The same program on Linux, with its 8 MiB stack, gets about eight times deeper — past 2,000 calls — before it's killed with exit status 139.

Most recursions are fine: the stack only needs to be as deep as the recursion, and walking a balanced tree of a billion items takes about 30 levels. The danger is recursion whose depth depends on the input — a linked list, a degenerate tree, a deeply nested JSON document — and large local arrays, especially in threads, whose stacks are often smaller.

What optimization does to calls

A call costs more than the work it wraps when the function is tiny: moving arguments into registers, the call, building and tearing down the frame, the ret. Optimizing compilers remove that overhead in two ways.

Inlining copies the body of a small function into its caller. With clang -O2:

static int square(int x) { return x * x; }
int f(int a) { return square(a) + 1; }

f:
    imul edi, edi          ; square, inlined
    lea  eax, [rdi+1]      ; + 1
    ret

There's no call left, and no square function in the output at all. Inlining is also what makes other optimizations possible, because the compiler can now see both sides of the call at once.

Recursion can become a loop. The recursive fact above, compiled with clang -O2 (with vectorization turned off to keep it readable), contains no call:

fact:
    mov  eax, 1            ; the running product
    cmp  edi, 2
    jl   .done
.loop:
    imul eax, edi          ; product *= n
    cmp  edi, 2
    lea  ecx, [rdi-1]
    mov  edi, ecx          ; n = n - 1
    ja   .loop
.done:
    ret

The compiler noticed that the multiplication could be accumulated in a variable as it goes, and rewrote the recursion as a loop using one frame instead of n. With its default settings clang goes further still and vectorizes that loop with SSE instructions, multiplying four numbers at a time. The general case is tail call elimination: when a call is the very last thing a function does, its frame can be reused, and the call becomes a jump — like the jmp rax in the optimized apply from the previous chapter. C compilers do this as an optimization, not a guarantee, so C code can't rely on it; languages like Scheme require it.

This matters when reading binaries: in optimized code, small functions have vanished into their callers, recursive functions may be loops, and the call graph in the source no longer matches the one in the machine code.

Beyond the stack: coroutines

A function call follows strict nesting: the callee finishes before the caller continues, so frames can live on a stack. Tanenbaum's book also describes coroutines, which break that rule: two routines resume each other, each continuing where it last stopped. Their state can't live in a stack frame that's thrown away at each switch.

Modern languages have made this common. Python's generators, and async functions in JavaScript, Python, C#, Rust and C++20, can suspend in the middle and resume later. Their compilers keep the suspended function's local variables in an object on the heap, rather than in a stack frame, so they survive between resumptions.

Takeaways

• Every call gets its own stack frame with its own copy of every parameter and local. That's what makes recursion work: five active fact calls, five different n.
• C passes arguments by value; to modify the caller's variable, pass its address.
• Locals die when the function returns: a pointer to one is dangling, and the next call reuses the memory.
• The stack is small and fixed — 8 MiB on Linux, 1 MiB on Windows by default. Recursion that goes too deep hits the unmapped guard region: a stack overflow.
• Optimizers inline small functions and turn recursion into loops (tail calls), so optimized machine code may not have the calls you wrote.
• Coroutines, generators and async functions suspend mid-call; their state lives on the heap instead of the stack.