Tracing Recursion and Counting Calls: short notes (Programming in C)

Introduction

For a short recursive C function there are four things to determine: what it prints, what it returns, how many times it is called (or how many times some line runs), or what a variable holds afterwards. Each has a reliable mechanical method. This note gives those methods and applies them to the standard patterns: output before and after a call, two recursive calls, static variables, pointer parameters, and nested recursion.

The concepts behind recursion (base cases, frames, forms of recursion) are in Recursion. Every output and count in this note was produced by running the code.

Conventions: C11; outputs are for gcc on x86-64 Linux. "Calls" counts every invocation, including the top-level one and calls that return immediately at a base case.

Prerequisites

Recursion: frames, winding and unwinding, recursion trees.

Core concepts: four methods

Method 1: the recursion tree (for output and call counts)

Draw one node per call, children in the order the calls are made. Then:

Number of calls = number of nodes.
Output order: walk the tree depth first, left to right. A printf that comes before the recursive calls in the body prints when the walk first reaches the node (preorder); one that comes between two calls prints between visiting the first and second child (inorder); one that comes after prints when the walk leaves the node (postorder). This is exactly Binary Tree Traversals.

Method 2: the bottom-up value table (for return values)

When the return value depends only on the argument, compute $f(0), f(1), f(2), \ldots$ from the base cases upward, writing a table, until you reach the requested argument. This avoids re-expanding the same subcall many times.

Method 3: a recurrence (for counts as a function of $n$ )

Let $C(n)$ be the number of calls made by f(n). Read it off the code: 1 for the call itself plus the calls of each recursive invocation. Do the same for "number of times line X runs" or "number of additions". Then solve, or simply tabulate for the small $n$ asked.

Method 4: the frame table (for `static`, global and pointer state)

When a function changes state that outlives a single call (a static local, a global, or an object reached through a pointer), the bottom-up table no longer works, because the result depends on the order in which calls happen. Write a table with one row per event, in execution order: call, change of state, return value. A static local has one copy shared by every activation, initialised once before the program starts (Scope, Storage Classes and Linkage).

How it works: standard patterns

Pattern A: print before and after

C

void sandwich(int n) {
    if (n <= 0) return;
    printf("%d ", n);      /* while winding */
    sandwich(n - 1);
    printf("%d ", n);      /* while unwinding */
}

sandwich(3) prints 3 2 1 1 2 3 and makes 4 calls ( $n = 3, 2, 1, 0$ ). For nonnegative integer $n$ , with sufficient execution resources, it makes $n + 1$ calls and prints $2n$ numbers.

Pattern B: two calls with output between them

C

void g(int n) {
    if (n <= 1) { printf("%d ", n); return; }
    g(n - 1);
    printf("%d ", n);
    g(n - 2);
}

Trace of g(4): recursion tree and output order — Figure 1. The recursion tree of g(4) with each node numbered in the order its printf runs, and the trace table listing, step by step, the active call, the action (call, print or return) and the output so far. Output: 1 2 0 3 1 4 1 2 0; 9 calls.

g(4) prints 1 2 0 3 1 4 1 2 0 and makes 9 calls. The call count satisfies $C(n) = 1 + C(n-1) + C(n-2)$ with $C(0) = C(1) = 1$ , the same recurrence as naive Fibonacci, so $C(n) = 2F_{n+1} - 1$ (here $2 \cdot 5 - 1 = 9$ ).

Pattern C: doubling recursion

C

void p(int n) { if (n > 0) { p(n - 1); printf("*"); p(n - 1); } }

For nonnegative integer $n$ , mathematical counts are as follows (bounded C execution also requires all intermediate values to fit and sufficient stack). Stars: $S(n) = 2S(n-1) + 1$ , $S(0) = 0$ , so $S(n) = 2^n - 1$ . Calls: $C(n) = 2C(n-1) + 1$ , $C(0) = 1$ , so $C(n) = 2^{n+1} - 1$ . For $n = 4$ : 15 stars and 31 calls. This is the Tower of Hanoi recurrence (Recursion).

Pattern D: a `static` variable

C

int f(int n) {
    static int r = 0;
    if (n <= 0) return 1;
    if (n > 3) { r = n; return f(n - 2) + 2; }
    return f(n - 1) + r;
}

Frame table for f(5):

Step	Call	Action	`r` after	Returns
1	`f(5)`	$5 > 3$ : set `r = 5`, call `f(3)`	5	$f(3) + 2$
2	`f(3)`	call `f(2)`	5	$f(2) + r$
3	`f(2)`	call `f(1)`	5	$f(1) + r$
4	`f(1)`	call `f(0)`	5	$f(0) + r$
5	`f(0)`	base case	5	1

Unwinding: $f(1) = 1 + 5 = 6$ , $f(2) = 11$ , $f(3) = 16$ , $f(5) = 18$ . The value is well defined here because no call that runs during f(n - 1) changes r again; in return f(n - 1) + r; the read of r and the call are indeterminately sequenced, so if the callee did modify r, the result could depend on the compiler's choice of order (Operators and Expressions).

Automatic versus static. Compare

C

int cnt_auto(int n)   { int c = 0; if (n <= 0) return 0; c++; return c + cnt_auto(n - 1); }
int cnt_static(int n) { static int c = 0; if (n <= 0) return c; c++; int r = cnt_static(n - 1); return r + c; }

cnt_auto(4) is 4: each frame has its own c, equal to 1. cnt_static(4) is 20: c reaches 4 on the way down, the base case returns 4, and each of the four levels adds the shared c, now 4, giving $4 + 4 \cdot 4$ . For nonnegative $n$ and a fresh static counter initially zero, assuming all arithmetic fits, $n + n^2$ . A second call cnt_static(4) in the same program would give a different value, because c is not reset.

Pattern E: state through a pointer

C

void ref(int *x, int n) { if (n == 0) return; *x += n; ref(x, n - 1); *x *= 2; }

The routine requires nonnegative n, a live int pointer, all intermediate arithmetic to fit, and sufficient stack. With x = 0, ref(&x, 3): winding adds 3, 2, 1 (giving 6); unwinding doubles three times, giving 48. In general all additions happen first and all doublings afterwards: $x = 2^n \cdot n(n+1)/2$ . Swapping the two statements around the call would interleave them differently, so always separate winding work from unwinding work.

Pattern F: return value with two calls

C

int foo(int n) { if (n <= 2) return 1; return foo(n - 1) + foo(n - 3); }

Value table (Method 2), using $f(0) = f(1) = f(2) = 1$ :

$n$	0	1	2	3	4	5	6	7	8
$f(n)$	1	1	1	2	3	4	6	9	13

So foo(8) is 13. Because every leaf of the recursion tree returns 1 and every internal node adds its two children, the tree has 13 leaves and therefore $13 - 1 = 12$ internal nodes: $25$ calls in total. In general, for a function whose base cases all return 1 and whose recursive case adds exactly two calls, calls $= 2 f(n) - 1$ .

Pattern G: nested recursion (Ackermann)

C

int A(int m, int n) {
    if (m == 0) return n + 1;
    if (n == 0) return A(m - 1, 1);
    return A(m - 1, A(m, n - 1));
}

The mathematical Ackermann function requires $m,n\ge0$ ; this C routine is restricted to tiny arguments whose intermediates fit int and available stack. Small values follow by induction: $A(1, n) = n + 2$ , $A(2, n) = 2n + 3$ , $A(3, n) = 2^{n+3} - 3$ . A(2, 3) is 9 and takes 44 calls; A(3, 3) is 61. It is the standard example of a computable function that is not primitive recursive, and its values explode so fast that only tiny arguments appear in questions.

Worked examples

All outputs below are for C11 with gcc on x86-64 Linux (LP64).

Example 1. sandwich(3): output 3 2 1 1 2 3, 4 calls.

Example 2. g(4): output 1 2 0 3 1 4 1 2 0, 9 calls.

Example 3. p(4): 15 stars, 31 calls.

Example 4. f(5) with the static variable: 18.

Example 5. cnt_auto(4) is 4; cnt_static(4) is 20.

Example 6. ref(&x, 3) from x = 0: 48.

Example 7. foo(8): value 13, 25 calls.

Example 8. A(2, 3): 9, with 44 calls.

Important properties and observations

Output position in the body decides preorder-like, inorder-like or postorder-like printing.
Calls = nodes of the recursion tree; for "sum of two calls with base value 1", calls $= 2f(n) - 1$ .
A static local is shared by every activation and keeps its value between top-level calls; an automatic local is per activation.
On a single recursive chain, pointer updates after the recursive call unwind in reverse call order. In branching recursion, entry and exit updates follow preorder and postorder of the ordered recursion tree, retaining sibling order.
In an expression such as f(n - 1) + r, the order of the call and the read of r is not fixed by C; this matters only if the callee modifies r.
Use tables, not mental arithmetic: write one row per call or per value.

GATE examination perspective

"What is printed?" Draw the recursion tree and place each printf as pre, in or post.
"What is returned?" Build the bottom-up value table, unless static, global or pointer state is involved; then use the frame table.
"How many calls / how many times is line X executed?" Write the recurrence and tabulate.
Static versus automatic locals in recursive code, and repeated top-level calls.
Complexity of the function, from the recurrence (Solving Recurrences).

Summary

Recursion: prerequisite.
Scope, Storage Classes and Linkage: related. static locals.
Functions and Parameter Passing: related. Pointer parameters.
Binary Tree Traversals: related. Pre, in and post order.
Solving Recurrences and the Master Theorem: dependent.
Recurrence Relations: related.

Tracing Recursion and Counting Calls

Introduction

Prerequisites

Core concepts: four methods

Method 1: the recursion tree (for output and call counts)

Method 2: the bottom-up value table (for return values)

Method 3: a recurrence (for counts as a function of $n$ )

Method 4: the frame table (for `static`, global and pointer state)

How it works: standard patterns

Pattern A: print before and after

Pattern B: two calls with output between them

Pattern C: doubling recursion

Pattern D: a `static` variable

Pattern E: state through a pointer

Pattern F: return value with two calls

Pattern G: nested recursion (Ackermann)

Worked examples

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts: four methods

Method 1: the recursion tree (for output and call counts)

Method 2: the bottom-up value table (for return values)

Method 3: a recurrence (for counts as a function of nnn)

Method 4: the frame table (for static, global and pointer state)

How it works: standard patterns

Pattern A: print before and after

Pattern B: two calls with output between them

Pattern C: doubling recursion

Pattern D: a static variable

Pattern E: state through a pointer

Pattern F: return value with two calls

Pattern G: nested recursion (Ackermann)

Worked examples

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps

Method 3: a recurrence (for counts as a function of $n$ )

Method 4: the frame table (for `static`, global and pointer state)

Pattern D: a `static` variable