Why functions need a treaty
In the previous guide a procedure call jumped away and the return address brought it home. But a real program is a crowd of functions, many written by people who never met, compiled separately, perhaps in different years. When your code calls a library routine, where does it leave the arguments? Which registers is the routine allowed to scribble over, and which must it hand back untouched? If everyone guessed, nothing would interoperate. The fix is a calling convention: a treaty, written down once for an ISA, that every compiler and every assembly programmer agrees to obey.
Think of it like booking a meeting room shared by strangers. The treaty says: leave your message on these specific tags by the door (the argument registers), the room number for your reply goes here (the return-value register), and whatever you find on the whiteboard you must either leave as-is or photograph and restore before you go. The convention is not part of the silicon — the hardware happily lets you break it — but break it and you will return to a caller whose state has been quietly wrecked.
Who saves what: caller vs callee
The treaty's sharpest clause splits the register file into two camps. Some registers are caller-saved (also called volatile or scratch): a called function may freely clobber them, so if the caller still needs a value there, the caller must spill it to the stack before the call and reload it after. Other registers are callee-saved (preserved): a function that wants to use one must first save the old contents and restore them before returning, so the caller sees them unchanged. The whole caller- versus callee-saved scheme is a careful bargain about who pays the cost of saving.
Why split it at all instead of always saving everything? Because saving is work — every spill is a memory store. Splitting lets each side save only what it actually cares about. A caller that holds nothing valuable across a call saves nothing; a leaf function that needs only scratch registers saves nothing either. The convention picks the division so that, on average, the fewest stores and loads happen. It is a small worked example of the architecture mantra to make the common case fast.
The stack frame: one room per call
Each active call gets its own private slab of stack memory called a stack frame (or activation record). When a function is entered it pushes the stack pointer down by a fixed amount, carving out room for its saved registers, its local variables, and any arguments it must pass onward. When it returns, it pops that exact amount back, erasing the room as if it were never there. The chain of frames stacked on top of one another is, quite literally, the program's history of who-called-whom, frozen in memory.
Many conventions also keep a frame pointer — a second register pinned to the start of the current frame while the stack pointer wanders as the function pushes and pops. With the frame pointer fixed, every local lives at a constant offset from it, which makes debuggers and stack traces far easier to walk. Optimizing compilers often drop the frame pointer to free up that register, computing offsets from the stack pointer instead; that is faster but is exactly why some optimized crash dumps are hard to read.
high addresses +---------------------+ | caller's frame | +---------------------+ <- frame pointer (fp) | saved return addr | | saved callee regs | | local variables | | outgoing arguments | +---------------------+ <- stack pointer (sp), grows downward low addresses
Recursion is just frames stacked up
Here is the payoff. Recursion looks mysterious — a function calling itself — but to the stack it is nothing special. Each call simply gets its own fresh stack frame, with its own private copy of the locals and its own saved return address. The function does not know or care that the caller happens to be another copy of itself. Recursion on the stack works for exactly the same reason an ordinary call does: every activation is bookkept separately.
- Call factorial(3). A frame is pushed holding n=3 and the return address back to the original caller.
- Since n is not 1, it calls factorial(2). A second frame goes on top, holding n=2 and the return address pointing back into factorial(3).
- factorial(2) calls factorial(1). A third frame, n=1, with its return address pointing into factorial(2). The stack is now three frames deep.
- factorial(1) hits the base case, returns 1, and pops its frame. Control follows the return address back into factorial(2).
- Each frame unwinds in turn: factorial(2) computes 2 x 1 = 2 and returns; factorial(3) computes 3 x 2 = 6 and returns. The stack is empty again, with the answer 6 in hand.
Notice that nothing in the hardware "knows" about recursion. The stack pointer just kept marching down and back up, and the saved return addresses formed a trail of breadcrumbs leading home one step at a time. The only resource recursion consumes is stack space — one frame per pending call. Run a recursion too deep and you exhaust the stack region: that is the dreaded stack overflow, and it is why an unbounded recursion crashes rather than running forever.
Honest caveats and the bigger picture
A few honest qualifications. First, the exact convention — which registers carry arguments, how many before spilling to the stack, how structs are passed — differs by ISA and even by operating system on the same ISA, which is why an x86-64 Linux binary cannot simply call a Windows function. The principle is universal; the specific tags on the door are not. Second, recursion is elegant but not free: each frame costs memory and a couple of stores and loads, so a deep recursion can be slower and more memory-hungry than an equivalent loop with the same result. Compilers sometimes rescue tail recursion by reusing one frame, but you cannot count on it.
Step back and see how much was built from how little. The stack is just memory and a pointer; the convention is just an agreement; recursion is just frames. Yet together they let strangers' code cooperate, let functions nest arbitrarily deep, and let a self-referential definition compute a concrete answer. The next guide leaves the running program and asks how all these separately compiled pieces got glued together in the first place — the linker and loader — and how a program finally talks to the operating system through the system call.