Recursion in C: Stack Frames, a Hand-Tracing Method and Solved GATE Questions

Recursion questions become difficult when you try to hold the whole call tree in your head. That is also how print order, return values and call counts get mixed together.

Use a fixed paper method instead: draw each call as a stack frame, mark statements before and after the recursive call, and evaluate returns only while unwinding. The answer then comes from the trace, not a guess.

What happens during a recursive call

A recursive function needs two logical parts. The base case stops further calls. The recursive case moves the input toward that base case. If the input never reaches the base case, calls continue until the program exhausts its available stack space.

Each active call gets its own stack frame. A frame normally contains that call's parameters, local variables, return address and saved execution state. If fun(3) calls fun(2), the frame for fun(3) remains suspended. Its local n does not turn into 2. The child has a separate parameter with value 2.

Two moments control most output questions:

• Descent: statements before the recursive call execute as the stack grows.

• Unwind: statements after the recursive call execute as completed frames return.

First check termination. Then draw the descent. Finally read the unwind from the deepest completed call back to the first caller.

Trace return-value accumulation with factorial

Consider this function:

int fact(int n) {
    if (n == 0) return 1;
    return n * fact(n - 1);
}

For fact(4), write the unresolved calls downward:

fact(4) = 4 * fact(3)

fact(3) = 3 * fact(2)

fact(2) = 2 * fact(1)

fact(1) = 1 * fact(0)

fact(0) = 1

Only the last line is immediately complete. Now fill returned values upward:

1. fact(0) returns 1.

2. fact(1) returns 1 * 1 = 1.

3. fact(2) returns 2 * 1 = 2.

4. fact(3) returns 3 * 2 = 6.

5. fact(4) returns 4 * 6 = 24.

The final answer is 24. Notice that multiplication does not finish on descent. Each frame is waiting for the value produced below it. Writing an incomplete expression beside every frame prevents you from multiplying in the wrong order or skipping a call.

The maximum number of simultaneously active calls here is five, from fact(4) through fact(0). Whether a question calls that depth five or counts four recursive edges depends on its wording, so distinguish frames from call transitions.

Trace prints before and after the call

Now use a function with output on both sides of recursion:

void fun(int n) {
    if (n > 0) {
        printf("%d ", n);
        fun(n - 1);
        printf("%d ", n);
    }
}

Trace fun(3). The first printf runs before the recursive call, so descent prints 3, then 2, then 1. fun(0) fails the condition and prints nothing.

The deepest non-empty frame, fun(1), now resumes after its recursive call and prints 1. Then fun(2) resumes and prints 2. Finally fun(3) resumes and prints 3.

The complete output is:

3 2 1 1 2 3

This is a reusable pattern. A print before a single fun(n-1) call appears in descending order. A print after it appears in ascending order. When both exist, the base case is the turning point between the two halves.

Count recursive calls and maximum stack depth

Some questions ask for work rather than output. For naive Fibonacci,

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

let T(n) be the total number of calls, including the initial call. Then T(0)=1, T(1)=1, and

T(n) = 1 + T(n-1) + T(n-2) for n >= 2.

For n=4, compute rather than guess:

• T(2) = 1 + 1 + 1 = 3.

• T(3) = 1 + 3 + 1 = 5.

• T(4) = 1 + 5 + 3 = 9.

The closed form for this call count is T(n) = 2*fib(n+1) - 1. Since fib(5)=5, it confirms T(4)=2*5-1=9.

Call count is not stack depth. Naive Fibonacci makes exponentially many total calls, but only one branch is active at a time. Its deepest branch reduces n by 1 repeatedly, so maximum depth remains O(n). Linear factorial recursion also uses O(n) active frames, while making only linear total calls.

Traps that flip a recursion answer

Wrong base case: check whether every path reaches it. For a decreasing positive n, a condition that stops only at an unreachable value causes unbounded recursion.

Post-decrement argument: fun(n--) passes the old value of n to the child. The child can receive the same value instead of n-1, so the recursion may make no progress. Trace the value actually passed, not the value left in the parent afterward.

Print placement: output before the call belongs to descent. Output after the call belongs to unwind. Moving one line across the call reverses its order.

Discarded return: writing fact(n-1); return n; calls the child but ignores its result. A recursive value affects the answer only if the caller uses or returns it.

Pass by value: each frame has its own n. A child's assignment to its parameter does not overwrite the parent's parameter.

For staple implementations, Classic Programs in C, Java and Python puts factorial, Fibonacci and GCD beside other tracing exercises. C Programming for Teaching CS Exams connects recursion to the wider language syllabus.

Solved GATE questions on recursion in C

GATE asks for printed output, a returned value, a total call count, the maximum active depth, or the edit that breaks termination. Decide each answer on paper before reading the explanation under it.

GATE 2017: what foo(3) and bar(3) actually do

int foo(int val) {
    int x = 0;
    while (val > 0) {
        x = x + foo(val--);
    }
    return val;
}

int bar(int val) {
    int x = 0;
    while (val > 0) {
        x = x + bar(val - 1);
    }
    return val;
}

Invocations of foo(3) and bar(3) will result in: (A) return of 6 and 6 respectively; (B) infinite loop and abnormal termination respectively; (C) abnormal termination and infinite loop respectively; (D) both terminating abnormally.

Answer: (C). In foo, val-- hands the child the current value and decrements only afterwards, so foo(3) calls foo(3) again. Every repeat adds a frame, the stack runs out, and the program aborts. In bar, the argument val - 1 does shrink, so each child reaches the base condition and returns, but val in the parent never changes and the while loop repeats forever at a fixed depth. One failure exhausts frames, the other never leaves one. Re-attempt it cold in the basic recursion practice set.

GATE 2009: the output of fun(5, &x)

#include <stdio.h>

int fun(int n, int *f_p) {
    int t, f;
    if (n <= 1) {
        *f_p = 1;
        return 1;
    }
    t = fun(n - 1, f_p);
    f = t + *f_p;
    *f_p = t;
    return f;
}

int main() {
    int x = 15;
    printf("%d\n", fun(5, &x));
    return 0;
}

The printed value is: (A) 6; (B) 8; (C) 14; (D) 15.

Answer: (B) 8. The initial 15 never matters, because the deepest call writes 1 into *f_p before any caller reads it. Fill the returns upward and keep the pointer value beside each frame. fun(1) returns 1 and leaves *f_p = 1. fun(2) returns 1 + 1 = 2 and leaves *f_p = 1. fun(3) returns 2 + 1 = 3 and leaves *f_p = 2. fun(4) returns 3 + 2 = 5 and leaves *f_p = 3. fun(5) returns 5 + 3 = 8. That is Fibonacci again, reached in five calls rather than the fifteen the naive version needs at n = 5, because the shared pointer carries the previous value instead of recomputing it. The recursion with pointers set has more of this shape.

GATE 2005: space complexity when one call spawns many

double foo(int n) {
    int i;
    double sum;
    if (n == 0) return 1.0;
    else {
        sum = 0.0;
        for (i = 0; i < n; i++)
            sum += foo(i);
        return sum;
    }
}

The space complexity of the above function is: (A) O(1); (B) O(n); (C) O(n!); (D) O(n^n).

Answer: (B) O(n). The loop fires n separate children, so the total number of calls grows explosively. The number of frames alive at one moment does not. The loop starts foo(i) only after the previous child has returned, so the longest live chain is foo(n), foo(n-1), down to foo(0), which is n + 1 frames. Space follows the depth, not the count. Time Complexity Analysis practice carries the rest of these depth-versus-count questions.

The Programming and Data Structures syllabus wording for the current cycle sits on the official GATE portal run by that year's organising IIT.

For a longer drill, Basic Recursion MCQs: 12 Solved C Questions works through twelve more, including static state that survives a return and a sum that never reaches main. The question bank holds more than 900 C programming questions, about 70 of them on basic recursion. Practise on paper, because recognising code is not the same as producing the correct trace under time pressure.

The short version and next step

Write the call chain down, settle the base case, and fill returns upward. Prints before a call follow descent; prints after it follow unwind. Count total calls and active depth separately.

Use the C Programming course for structured practice, then follow the broader Coding Skills category. On the next recursive program you meet, draw the frames before looking at the options.