C / FUNCTIONS
Recursion and the stack frame it costs
Trace a recursion frame by frame, estimate the stack it costs from depth and frame size, and rewrite it as a loop when depth is unbounded.
What you will learn
- Trace which frames are alive at the deepest point of a recursive call
- Turn an accumulator-style recursion into a while loop that uses one frame
- Estimate stack use as depth times frame size against an 8 MB default limit
- Bound recursion with a depth parameter when input decides how deep it goes
Understanding Recursion and the stack frame it costs
A call does not finish when it makes another call. While fact(4) is waiting on fact(3), the value 4, the address to continue from after the call returns, and any registers the callee will clobber still have to live somewhere, and that somewhere is a stack frame pushed for each active call. Recursion uses exactly the same call mechanism as anything else; the only difference is that several frames belonging to the same function are alive at once, each with its own private copy of n. That is the whole mental model: the stack is C's record of where you were and what you still owe.
The stack is a fixed-size region reserved when the thread starts, commonly 8 MB for the main thread on Linux, 1 MB on Windows, and often far less for threads you create yourself, and nothing in the language compares your depth against it. Running off the end is undefined behaviour; in practice you get SIGSEGV and a backtrace of thousands of identical lines, with no warning from the compiler. So the number to reason about is depth times frame size: two scalars plus call overhead is a few dozen bytes per level, but a function declaring char line[4096] costs over 4 KB per level and dies around depth 2000. Depth is the cost, not total call count, which is why recursing over a balanced tree of a million nodes only nests about twenty frames deep.
A frame has to survive the recursive call only when work remains after it returns, such as the pending n * in factorial or a putchar placed after the call. When the recursive call is the last thing the function does and its result is returned unchanged, the frame holds nothing anyone will read again, and gcc or clang at -O2 will usually reuse it and compile the call into a jump. C does not require that, unlike Scheme, so the same source compiled -O0 for debugging really does stack up every frame; if the depth matters, write the loop yourself. For genuinely recursive shapes like trees, either cap the depth or keep your own explicit stack array, which you can size and check.
<stdio.h>
static unsigned long long fact(unsigned n, int depth)
{
unsigned long long inner;
printf("%*senter fact(%u)\n", depth * 2, "", n);
if (n <= 1) {
printf("%*sbase: return 1\n", (depth + 1) * 2, "");
return 1;
}
inner = fact(n - 1, depth + 1); /* this frame stops here and waits */
printf("%*sresume fact(%u): %u * %llu = %llu\n",
depth * 2, "", n, n, inner, n * inner);
return n * inner;
}
int main(void)
{
printf("fact(4) = %llu\n", fact(4, 0));
return 0;
}
Every call that is still in progress owns a private stack frame, so recursion pays memory proportional to its maximum depth.
Worked examples
Work after the call keeps the frame alive
Printing after the recursive call reverses a string, because each frame resumes in the opposite order it was pushed.
<stdio.h>
static void print_reversed(const char *s)
{
if (*s == '\0')
return; /* deepest frame prints nothing */
print_reversed(s + 1); /* every frame exists before any output */
putchar(*s); /* runs as this frame unwinds */
}
int main(void)
{
print_reversed("stack");
putchar('\n');
return 0;
}
Example explained
Line 1The base case is the frame that sees the terminator; it returns without printing anything.
Line 2print_reversed(s + 1) comes before putchar, so all six frames are live before the first character appears.
Line 3Each putchar reads the s stored in its own frame, which is why output runs from the last letter back to the first.
Line 4Depth here equals the string length, so this function on a 10 MB string would need 10 million frames and crash.
One frame instead of a thousand
An accumulator-passing recursion and a loop compute the same sum, but only one of them keeps its stack use constant.
<stdio.h>
static unsigned long sum_rec(unsigned n, unsigned long acc)
{
if (n == 0)
return acc; /* answer already complete here */
return sum_rec(n - 1, acc + n); /* tail position */
}
static unsigned long sum_loop(unsigned n)
{
unsigned long acc = 0;
while (n != 0) {
acc += n;
n--;
}
return acc;
}
int main(void)
{
printf("recursive: %lu\n", sum_rec(1000, 0));
printf("loop: %lu\n", sum_loop(1000));
return 0;
}
Example explained
Line 1sum_rec carries the running total forward, so nothing in a frame is needed after its recursive call returns.
Line 2That makes it a tail call, which an optimizer may turn into a jump, but at -O0 all 1000 frames are really pushed.
Line 3sum_loop keeps acc in a single frame and performs the same 1000 additions with no stack growth.
Line 4Identical results, identical arithmetic; the only difference is how much stack the shape of the code demands.
Bounding depth when the input decides it
A recursive list sum that refuses to recurse past a fixed depth instead of trusting the data to be short.
<stdio.h>
MAX_DEPTH
struct node { int v; struct node *next; };
/* 0 on success, -1 if the list is deeper than we are willing to nest */
static int sum_bounded(const struct node *p, int depth, long *sum)
{
long rest;
if (p == NULL) {
*sum = 0;
return 0;
}
if (depth >= MAX_DEPTH)
return -1;
if (sum_bounded(p->next, depth + 1, &rest) != 0)
return -1;
*sum = p->v + rest;
return 0;
}
int main(void)
{
struct node c = { 3, NULL };
struct node b = { 2, &c };
struct node a = { 1, &b };
struct node d = { 4, &a };
long sum;
if (sum_bounded(&a, 0, &sum) == 0)
printf("sum = %ld\n", sum);
else
printf("list too deep\n");
if (sum_bounded(&d, 0, &sum) == 0)
printf("sum = %ld\n", sum);
else
printf("list too deep\n");
return 0;
}
Example explained
Line 1The depth parameter is the only thing limiting frame count, since list length comes from data rather than from code.
Line 2The check sits before the recursive call, so the limit is enforced one frame before it would be exceeded.
Line 3Returning -1 propagates upward, and each return pops one waiting frame off the stack.
Line 4The second list is four nodes long, one past MAX_DEPTH, so no partial sum is produced.
Important notes
Stack overflow is undefined behaviour in C: there is no portable way to ask how much stack is left or to recover, and the crash usually points at a line that is perfectly correct.
sizeof your locals underestimates a frame; the return address, saved registers, spilled temporaries and alignment padding are in there too.
Common mistakes
Writing the base case as if (n >= 0) return ... for an unsigned parameter: unsigned values are never negative, so the test never fires and n - 1 wraps to UINT_MAX, recursing until SIGSEGV.
Declaring a large local such as char buf[8192] inside the recursive function: every level allocates its own copy, so depth 1000 needs 8 MB of stack and overflows even though the algorithm is cheap.
Testing a 100000-deep recursion at -O2, where the tail call became a jump, then crashing in the -O0 debug build where all the frames are real.
Returning the address of a local from a recursive helper: the frame is popped on return, so the caller reads memory that the next call reuses.
Try it yourself
Change, predict, then run
Write void bits(unsigned n) that recurses on n / 2 while n > 1 and then prints '0' + n % 2 after the call returns, and run it on 37. State how many frames are alive at the instant the leftmost digit is printed.
Open the C workspaceCheck your understanding
Two recursive functions sum a 100000-node list. A returns node->value + sum(node->next). B passes a running total and returns sum(node->next, total + node->value). What is true about their stack use in C?
- B always runs in a single frame, because nothing is left to do after its recursive call.
- A runs in a single frame, because its addition happens before the call returns.
- Both can need 100000 live frames; B's tail call may become a jump, but C does not require that.
- Neither grows the stack, because compilers convert all recursion into loops.
Show answer
A cannot avoid the frames: the pending addition needs the caller's node pointer after the callee returns, so 100000 frames must coexist. B's call is in tail position and gcc or clang at -O2 typically reuses the frame, but that is an optimisation with no backing in the standard, so the same source at -O0 pushes all 100000 frames. Option 0 is tempting because tail calls are guaranteed to be space-efficient in languages like Scheme; C makes no such promise.