Recursion Tracing, Stack Frames & Static Variables
“Stack frames, activation trees, and static variable state accumulation.”
1.The Anatomy of a Function Call Frame (Activation Record)
§ 3.1.Whenever a function is invoked, the runtime system pushes an Activation Record (Stack Frame) onto the call stack containing:
1. Actual Parameters: Arguments passed to the function.
2. Return Address: Pointer to caller's instruction immediately following the call site.
3. Dynamic Link (Frame Pointer / EBP / RBP): Base pointer of caller's stack frame.
4. Local Automatic Variables: Storage for variables declared inside the function.
5. Saved Registers & Temporaries: Preserved CPU register state.
Recursion Mechanics:
Each recursive call creates its own independent frame with private local automatic variables. However, all calls share the same global and local static variables in the Data Segment!
2. GATE Worked Numerical: Recursion with Static Variables
Static variables are initialized ONLY ONCE at program startup in the Data Segment. Their values persist across all recursive calls!
Consider the recursive function:
int fun(int n) {
static int x = 0;
if (n <= 0) return 1;
x++;
return fun(n - 1) + x;
}
Find the value returned by fun(5).
Step 1: Trace calls going down the recursion stack:
fun(5): x becomes 1; calls fun(4)
fun(4): x becomes 2; calls fun(3)
fun(3): x becomes 3; calls fun(2)
fun(2): x becomes 4; calls fun(1)
fun(1): x becomes 5; calls fun(0)
fun(0): Base case hit (n <= 0)! Returns 1. At this instant, static variable x = 5.
Step 2: Trace unwinding going back up the recursion stack:
Note: In 'return fun(n - 1) + x;', when the call returns, 'x' is evaluated using its CURRENT global value (x = 5)!
fun(1) returns: fun(0) + x = 1 + 5 = 6.
fun(2) returns: fun(1) + x = 6 + 5 = 11.
fun(3) returns: fun(2) + x = 11 + 5 = 16.
fun(4) returns: fun(3) + x = 16 + 5 = 21.
fun(5) returns: fun(4) + x = 21 + 5 = 26.
Final returned result = 26.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
Systematic beginner-to-advanced C with clear examples.
Clear step-by-step C explanations — great for semester lab preparation.