Tracing Recursive C Functions with Activation Records and Return Values

Hello! In the previous lesson, you distinguished a fresh automatic variable from a block-scope static variable that retains its value. Recursion puts that distinction to work: several calls to the same function can be active at once, each with its own parameters and automatic variables.

This lesson will give you a reliable way to trace those calls, determine what each one returns, and calculate the final output. We will finish with a GATE CSE previous-year question and examine the mistakes its trace is designed to expose.

One function, several active calls

Consider a function computing factorial:

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

When fact(3) calls fact(2), the first call does not disappear. It pauses, still needing to multiply 3 by whatever fact(2) returns. That call may pause in turn while fact(1) runs. The program must retain each call’s parameter value and the place where execution should resume.

An activation record, or stack frame, represents one active invocation. For tracing purposes, record its parameters, its automatic local variables, and what it is waiting to do after a child call returns. A new call adds a frame; returning removes that frame and resumes its caller. Thus n in fact(3) and n in fact(2) are distinct parameter objects, even though both are named n.

Watch the central demonstration in Neso Academy’s Recursion in C. Its visual stack trace makes the difference between a call being paused and a call having returned particularly clear.

The picture is a useful logical model. In an output question, you usually need not draw physical memory addresses or the exact machine-level contents of a frame. You do need to keep each invocation’s state separate.

Trace downward, then calculate upward

Every terminating recursive trace has two directions. During descent, identify the next call and record what its caller is waiting for. At a base case, no further recursive call is made. During ascent, substitute each returned value into the paused caller’s computation.

For fact(3), descent reaches fact(0):

Only then can the waiting computations finish. fact(1) returns 1, fact(2) returns 2, and fact(3) returns 6. A return value travels to the immediate caller, not directly past all the intervening calls to main.

For a short chain, you can save time by writing the pending computations rather than drawing every frame:

fact(3): 3 * fact(2)
fact(2): 2 * fact(1)
fact(1): 1 * fact(0)
fact(0): 1

Work back upward from the last line. This is the same stack trace in a more compact exam-friendly form. The second part of Neso Academy’s demonstration develops that approach.

Before calculating any recursive program’s result, locate its base-case test and check that the calls on the path you are tracing can reach it. For example, fact(n - 1) reaches n == 0 when starting from a nonnegative integer. If a call never reaches a terminating case, there is no finite return trace to complete.

Printed output and shared state are separate from return values

A function can print on the way into recursion and again on the way out. The position of printf relative to the recursive call determines the order. In this example, calls is the one shared static object; mine and child belong to individual invocations.

#include <stdio.h>

int walk(int n) {
    static int calls = 0;
    int mine = n;

    ++calls;
    if (n == 0)
        return calls;

    int child = walk(n - 1);
    printf("%d %d %d\n", mine, child, calls);
    return mine + child;
}

int main(void) {
    printf("%d\n", walk(2));
    return 0;
}

The three invocations arrive with n equal to 2, 1, and 0, bringing calls to 3. The base-case invocation returns 3 without printing. Then walk(1) resumes: its own mine is still 1, child receives 3, and the shared calls is 3. It prints 1 3 3 and returns 4. Finally, walk(2) prints 2 4 3 and returns 6, which main prints.

1 3 3
2 4 3
6

The key distinction is that mine stays specific to a frame, while calls is shared by all frames. Also distinguish a value printed inside a call from the value that call returns: walk(1) prints a line but returns the single integer 4.

Not every recursive function forms one straight chain. With two separate calls, the trace branches:

int count(int n) {
    if (n <= 1)
        return 1;

    int left = count(n - 1);
    int right = count(n - 2);
    return left + right;
}

For count(3), the first child is count(2), which calls count(1) and count(0) and returns 2. The second child of count(3) is another invocation of count(1), returning 1. Therefore count(3) returns 3. There are five invocations in total, not three: the two calls with n == 1 are separate invocations, while 3 is the final return value.

The separate left and right statements make their call order explicit. If two calls instead appeared as the operands of + in one expression, do not assume C evaluates the left operand first; that order is not specified. Such a distinction matters when calls print or modify shared state.

A GATE previous-year trace: preserve the changing arguments

Now apply the same method to a GATE CSE 2016 question. It also uses a pointer argument, but only one pointer fact is needed here: if p designates an array element, p + 1 designates the next element; p[0] and p[1] refer to the current and next elements. Pointer arithmetic itself is the subject of the next lesson.

The function in the question is, with spacing expanded:

int f(int *p, int n) {
    if (n <= 1)
        return 0;
    else
        return max(f(p + 1, n - 1), p[0] - p[1]);
}

It is called with a = {3, 5, 2, 6, 4} and arguments f(a, 5). The question defines max as returning the larger of its two arguments. Each new frame has a different p and n. On descent, p advances one array position while n decreases by one:

The base-case test is important: the last call returns before attempting to read an element after a[4]. Now calculate the return values in reverse order. The frame examining 6, 4 returns max(0, 2) = 2. The frame examining 2, 6 returns max(2, -4) = 2. The frame examining 5, 2 returns max(2, 3) = 3. Finally, the first frame returns max(3, -2) = 3. The printed value is 3.

Notice a precision that helps with unfamiliar variants: the function compares every adjacent difference against the base-case value 0. For this particular array, the largest adjacent difference is 3, so both descriptions give the same answer. If all adjacent differences were negative, however, the function would return 0, not the largest of those negative differences.

When reviewing an incorrect trace of this question, diagnose where it diverged. Reading p[0] - p[1] in the opposite order changes the differences; keeping p fixed across calls examines the wrong pairs; and stopping at the base case without propagating 0 upward misses the actual comparisons. Each error has a different remedy, even if each produces a wrong final number.

Key takeaways

For each recursive invocation, record its own arguments and automatic locals, then note what it must do when its child returns. Find the base case on descent and propagate return values to immediate callers on ascent. Track printing separately from returning, and remember that a block-scope static variable is shared across invocations rather than copied into each frame.

The next lesson will make pointer and array expressions precise, including the p + 1 and p[1] operations used in the previous-year question.