What is C Recursion Call Stack- Free C Programming Course

🚀 Learn BLE on Linux (BlueZ) – Programming Part 1

Hands-on Bluetooth Low Energy course. Special price: ₹399

Enroll Now on Udemy →
💬 Need help or career guidance? Ask us!Contact Us →

Free C Programming Course • Functions • Lecture 40

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 static variables 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

Top of stack
Frame of dive(2): level=2, mine=21, return address into dive(1)
Below it
Frame of dive(1): level=1, mine=11, return address into dive(0)
Below it
Frame of dive(0): level=0, mine=1, return address into main
Bottom
Frame of main

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=11 and level 0 still sees mine=1. Each frame kept its own copy untouched.
  • Shared static: visits is 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.
PropertyAutomatic local variablestatic local variable
Where storedInside the stack frameFixed data area, not on the stack
Copies during recursionOne per active callExactly one shared copy
LifetimeUntil the call returnsEntire program run
Initial value if not setIndeterminateZero
ReentrancySafeNot 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

Level 0
hanoi(3,A,B,C)
Level 1
hanoi(2,A,C,B)hanoi(2,B,A,C)
Level 2
hanoi(1,A,B,C)hanoi(1,C,A,B)hanoi(1,B,C,A)hanoi(1,A,B,C)
Level 3
8 leaf calls hanoi(0,…) return at once

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 askWhy 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

MistakeResultRemedy
Forgetting the base caseInfinite descent and stack overflow crashWrite the base case first, then the recursive case
Expecting a local variable to be shared between callsEach call sees its own valuePass a pointer or use a carefully chosen static or global
Using a static variable as per-call stateValues leak between calls and break reentrancyUse automatic variables for per-call data
Putting work after the recursive call and expecting top-down orderOutput appears in reverseRemember unwinding runs in reverse order
Large local arrays in a recursive functionEach frame becomes huge, stack exhausted quicklyMove 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 -Wextra and, 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.

Continue the Free C Tutorial

Next: advantages and disadvantages of recursion, and how it compares with a plain loop.

💬 Need help or career guidance? Ask us!Contact Us →

2 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

×

🚀 BLE on Linux (BlueZ)

Hands-on course. Only ₹399

Enroll Now →