Part 4 of 7 · 2 min read
Stack growth
In plain words: Each function call puts a stack frame on the stack. The frame holds that call's local variables, its arguments and the address to return to. When the function returns, the frame is removed. A stack of plates is a fair picture: the last plate put on is the first one taken off.
On the common processors, new frames are placed at lower addresses. A small recursive function shows it:
#include <stdio.h>
void f(int n) {
int x;
printf("depth %d at %p\n", n, (void *)&x);
if (n < 3) f(n + 1);
}
int main(void) { f(0); return 0; }
Output:
depth 0 at 0x7fff8b1ea894
depth 1 at 0x7fff8b1ea864
depth 2 at 0x7fff8b1ea834
depth 3 at 0x7fff8b1ea804
Each call is at a lower address than the one before. The step between depths is hex 0x30, which is 3 × 16 = 48 bytes. So one frame of this function takes 48 bytes. A recursion that never stops keeps adding 48-byte frames until it reaches the stack limit. On the test machine ulimit -s printed 8192, meaning 8,192 kilobytes (8 MB). At 48 bytes per frame, that allows about 8,388,608 / 48 = 174,762 calls before the program is stopped by the system. The real figure is a little lower, because other things also use the stack.
Common mistake
Returning the address of a local variable is a bug. The variable lives in a frame that is removed when the function returns, so the address then points at memory that the next call will overwrite.
Check yourself: 1. In which direction do the addresses of new frames move on the machine above? 2. What is stored in a stack frame? 3. What happens to a frame when its function returns?