Need Help or More Information?
Questions about this free C programming course, embedded C training or career guidance? Get in touch.
C Recursion Call Stack
See exactly how recursive calls pile up, how every call gets its own local variables, and why stack depth is the number to watch in embedded C programming.
Understanding the C recursion call stack turns recursion from magic into mechanics. In this lecture of our free C programming course you will draw the call tree of the Tower of Hanoi, watch the winding and unwinding phases with a runnable demo, and learn why each recursive call owns a private copy of its local variables. This free C tutorial keeps one eye on C programming for embedded systems, where a few kilobytes of stack can decide whether your firmware survives.
What You Will Learn
- What a call tree is and how to draw one for a recursive function.
- What a stack frame contains and how frames are created and destroyed.
- The winding (descending) and unwinding (returning) phases of recursion.
- Why automatic local variables are separate in every call, and how
staticvariables behave differently. - How to count calls and measure maximum depth with a small program.
- How to think about stack usage on small microcontrollers.
Prerequisites
Complete the previous lecture on the Tower of Hanoi, or at least be comfortable with the factorial and Fibonacci recursion examples. You should know the difference between a parameter and a local variable and what static means for a variable declared inside a function.
How the C Recursion Call Stack Works
A function call in C is not free. Every time a function is called, the compiler-generated code reserves a block of memory on the call stack called a stack frame. That frame typically holds the arguments passed in, the local variables of that call, the address to jump back to when the function finishes, and sometimes saved processor registers. When the function returns, the frame is released and the caller continues exactly where it left off.
Recursion is nothing special to the processor. A recursive call simply creates one more frame on top of the same stack, using the same code but a fresh set of data. The language rule that makes this work is simple: every active call has its own parameters and its own automatic local variables.
Stack frames while dive(level 2) is running
Only the top frame is active. The frames below are paused, each waiting for the call above it to return.
Winding and Unwinding on the C Recursion Call Stack
Every recursive function runs in two phases. During winding, each call does its work up to the recursive call and then descends, adding a frame. When the base case is reached, unwinding begins: calls return one by one, and any code written after the recursive call now runs, in reverse order of the calls. Code before the recursive call runs top-down; code after it runs bottom-up. Knowing this is the key to predicting the output of any recursive function.
Runnable demo: enter, leave and local variables
#include <stdio.h>
static void dive(int level, int limit)
{
int mine = level * 10 + 1;
static int visits;
visits++;
printf("%*s> enter level %d, mine=%d, visits=%d\n", level * 2, "", level, mine, visits);
if (level < limit) {
dive(level + 1, limit);
}
printf("%*s< leave level %d, mine=%d, visits=%d\n", level * 2, "", level, mine, visits);
}
int main(void)
{
dive(0, 2);
return 0;
}
The %*s trick prints level * 2 blank characters, so deeper calls are indented and the nesting becomes visible. Compile and run it:
$ gcc -Wall -Wextra -std=c99 -o dive dive.c
$ ./dive
> enter level 0, mine=1, visits=1
> enter level 1, mine=11, visits=2
> enter level 2, mine=21, visits=3
< leave level 2, mine=21, visits=3
< leave level 1, mine=11, visits=3
< leave level 0, mine=1, visits=3
What the output proves
- Private locals: after the deeper calls come back, level 1 still sees
mine=11and level 0 still seesmine=1. Each frame kept its own copy untouched. - Shared static:
visitsis a single variable stored outside the stack. Every call increments the same one, so on the way back every level reports 3. - Reverse order: the leave messages appear in the opposite order to the enter messages, because the most recently created frame is the first to finish.
| Property | Automatic local variable | static local variable |
|---|---|---|
| Where stored | Inside the stack frame | Fixed data area, not on the stack |
| Copies during recursion | One per active call | Exactly one shared copy |
| Lifetime | Until the call returns | Entire program run |
| Initial value if not set | Indeterminate | Zero |
| Reentrancy | Safe | Not safe if shared state matters |
Drawing the Call Tree for the Tower of Hanoi
A call tree shows every call a recursive function makes, with children drawn under the call that created them. For three discs, the program from the previous lecture creates the tree below, written as hanoi(discs, from, via, to). Every leaf is a zero-disc call that returns immediately.
Call tree of hanoi(3, A, B, C): 15 calls in four levels
Read the tree left to right at each level and you can regenerate the move list: the moves are printed by the non-leaf calls in the order an in-order traversal visits them. The tree also shows two measurable facts: the total number of calls and the longest chain from the root to a leaf.
Measuring calls and depth with code
#include <stdio.h>
static unsigned long calls;
static int depth, max_depth;
static void hanoi_walk(int discs, char from, char via, char to)
{
calls++;
depth++;
if (depth > max_depth) {
max_depth = depth;
}
if (discs > 0) {
hanoi_walk(discs - 1, from, to, via);
hanoi_walk(discs - 1, via, from, to);
}
depth--;
}
int main(void)
{
int n;
printf("discs calls max_depth moves\n");
for (n = 1; n <= 8; n++) {
calls = 0;
max_depth = 0;
hanoi_walk(n, 'A', 'B', 'C');
printf("%5d %5lu %9d %5lu\n", n, calls, max_depth, (1UL << n) - 1);
}
return 0;
}
The function increments depth when it starts and decrements it just before returning, so depth always equals the number of active frames. Output:
discs calls max_depth moves
1 3 2 1
2 7 3 3
3 15 4 7
4 31 5 15
5 63 6 31
6 127 7 63
7 255 8 127
8 511 9 255
The pattern is clear: calls = 2n+1 − 1, maximum depth = n + 1, and moves = 2n − 1. Time grows exponentially while stack depth grows only linearly. This is the central lesson of this lecture: the number of calls and the depth of the stack are two different costs.
C Recursion Call Stack in Embedded Systems
On a desktop the stack is often measured in megabytes. On a microcontroller you might have only a few kilobytes of RAM shared between the stack, the heap and global data, and no operating system to warn you when the stack collides with other data. A frame holding two arguments, a few locals, a return address and saved registers may cost tens of bytes; multiply that by the maximum depth and compare the result with your stack budget.
| Question to ask | Why it matters |
|---|---|
| What is the worst-case recursion depth? | Depth times frame size is your stack cost |
| Is the depth bounded by input I do not control? | Unbounded input means a possible stack overflow |
| Can an interrupt arrive while the stack is deep? | Interrupt handlers need their own stack headroom |
| Does the safety standard allow recursion? | Several coding standards for safety-critical C restrict or forbid it |
Rule of thumb
Recursion is acceptable when the maximum depth is small and provably bounded, as in the Tower of Hanoi where depth equals the disc count. It is risky when depth depends on external data such as message nesting or user input.
Common Mistakes and Troubleshooting
| Mistake | Result | Remedy |
|---|---|---|
| Forgetting the base case | Infinite descent and stack overflow crash | Write the base case first, then the recursive case |
| Expecting a local variable to be shared between calls | Each call sees its own value | Pass a pointer or use a carefully chosen static or global |
| Using a static variable as per-call state | Values leak between calls and break reentrancy | Use automatic variables for per-call data |
| Putting work after the recursive call and expecting top-down order | Output appears in reverse | Remember unwinding runs in reverse order |
| Large local arrays in a recursive function | Each frame becomes huge, stack exhausted quickly | Move big buffers outside or pass a pointer to one buffer |
Warning: never declare a large array as a local variable inside a function that recurses. The array is duplicated in every frame, so a 1 KB buffer at depth 20 consumes 20 KB of stack.
Best Practices, Performance and Security
- Draw the call tree on paper for the smallest non-trivial input before you write the code.
- Treat the C recursion call stack as a budgeted resource, like flash or RAM. Keep recursive functions small, with few parameters and few locals, to keep each frame cheap.
- Add a depth counter during development, as in the demo above, to verify your worst-case estimate.
- Validate any input that influences the depth. An attacker-controlled depth is a classic stack-exhaustion vulnerability.
- Prefer an explicit loop when the depth is unbounded or the platform has very little RAM.
- Use compiler warnings such as
-Wall -Wextraand, where available, stack-usage reports to check your estimates.
Summary and Key Takeaways
- Every call, including a recursive one, gets its own stack frame.
- Parameters and automatic locals are private to each call; static variables are shared.
- Code before the recursive call runs while winding; code after it runs while unwinding, in reverse order.
- For Hanoi, calls = 2n+1 − 1 while stack depth is only n + 1.
- In embedded work, always compare worst-case depth times frame size against the stack budget.
Conclusion
You can now explain, draw and measure how recursion uses memory, and you know what the C recursion call stack holds at any moment. The call tree tells you how much time a recursive algorithm needs, the maximum depth tells you how much stack it needs, and the frame contents tell you why local variables never collide. That mental model is what separates a student who copies recursive code from an engineer who can size a stack. The next lecture of this free embedded C course compares recursion with iteration so you can decide which one fits a given job.
Frequently Asked Questions
What is a stack frame in C?
It is the block of stack memory created for one function call. It holds the call’s arguments, automatic local variables, the return address and sometimes saved registers, and it is released when the function returns.
Do recursive calls share local variables?
No. Each active call has its own copy of its parameters and automatic locals. Only static and global variables are shared across calls.
What is the difference between winding and unwinding in recursion?
Winding is the descent, where each call makes the next call and a new frame is added. Unwinding is the return path after the base case, where frames are removed in reverse order and code after the recursive call runs.
How can I find the maximum recursion depth of my function?
Add a global depth counter that is incremented on entry and decremented before every return, and record its maximum, exactly as the hanoi_walk demo does. Then run representative inputs.
Why does too much recursion crash a C program?
Each call consumes stack memory. When the stack space is exhausted the program overflows the stack, which usually ends in a segmentation fault on a PC and in silent memory corruption on many microcontrollers.
Is the C recursion call stack topic covered in this free C programming course?
Yes, this lecture is part of the Functions chapter of the EmbeddedPathashala free C programming course, written with embedded C programming in mind.
Need Help or More Information?
Questions about this free C programming course, embedded C training or career guidance? Get in touch.

2 Comments