Recursion total calls and active frames

Lesson 18 of 1915 minFree

Two counts answer two different questions

A function may be entered many times over a run while only a few invocations remain unfinished at any one moment. This lesson separates total invocations from maximum simultaneously active logical frames. You will count both for a small chain and then for a branching helper, without confusing either count with the returned value.

Prerequisites and placement

Read these three lessons first:

Recursion: base case and call stack: separate ordinary parameters, a waiting caller and a base-case invocation.
Recursion termination and base case design: the admitted input range and why every recursive step reaches a return.
Recursion: returned values and pending calculations: resume the exact caller statement after a child returns and keep returned values separate from arguments.

You also need ordinary C function calls, if, integer arithmetic and statement order. In the planned sequence this lesson follows Recursion over a bounded array prefix. No array or pointer operation is used here, so the three lessons above are sufficient to follow the examples independently.

Code and counting contract

Every example uses C11. For every helper in this lesson, admit starting int values from 0 through 4 only. All reached arguments remain in that range. All shown arithmetic and returned values fit even the minimum required range of int. Assume enough resources for these tiny runs. There are no global counters, static locals, shared pointer targets or concurrent calls in the learner code.

Apply the same counting convention throughout:

Count only invocations of the named recursive helper. Exclude main, printf and other library calls.
Include the initial invocation and every base-case invocation. If the initial call is itself a base case, it is one invocation, not two.
An invocation is active from entry until it returns, including time spent waiting for a child. An active caller need not be currently executing a statement.
Total calls increases by one on every entry; it never decreases when a call returns.
Current active frames increases on entry and decreases on return. The maximum active count is its largest value anywhere in that run.

A frame here is a logical record used to trace the source program. These counts do not specify physical machine frames, stack bytes or a safe general recursion limit. A compiler may transform the implementation while preserving required behavior.

First count a single-child chain

Predict the printed value, then separately count invocations and the maximum active frames.

#include <stdio.h>

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

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

For chain(3), the entered arguments are 3 → 2 → 1 → 0. Just after the base call enters and before it returns, all four calls are unfinished. The three older calls are waiting. Thus total invocations = 4 and maximum active frames = 4.

A complete event count is:

Enter argument 3: total so far 1, active 1.
Enter argument 2: total so far 2, active 2.
Enter argument 1: total so far 3, active 3.
Enter argument 0: total so far 4, active 4.
Return from argument 0 with 1: total stays 4, active becomes 3.
Return from argument 1 with 3: total stays 4, active becomes 2.
Return from argument 2 with 5: total stays 4, active becomes 1.
Return from argument 3 with 7: total stays 4, active becomes 0.

The program prints 7. That return value comes from the base 1 plus three additions of 2. It is neither of the call counts. At starting input 0, the helper returns 1 with total 1 and maximum active count 1.

For these straight chains, every invocation lies on one path, so total and maximum active counts agree. We must check the shape of the calls before carrying that equality to another function. Even for a chain, its number of calls depends on its exact step and stopping condition; it is not always the starting input plus one.

Now give each non-base call two children

Run this as a separate program. The two child calls are written in separate declaration statements.

#include <stdio.h>

int split(int n) {
    if (n == 0) {
        return 1;
    }
    int left = split(n - 1);
    int right = split(n - 1);
    return left + right;
}

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

At a positive argument, the entire first call must return before its result can finish initializing left. Only then does execution reach the declaration that calls the second child and initializes right. This statement sequence gives the first child’s entire subtree before the second child’s subtree. There is no need to assume a left-to-right order for multiple function calls inside one expression.

Both child statements call split(n - 1) using the caller’s own unchanged n. Equal arguments still create separate source-level invocations. The program has no saved-results lookup that replaces the second call with the first result. The waiting caller retains left while the second child runs, but the completed first child’s frame has already finished.

Termination is still easy to check on the admitted range. Each child receives a smaller nonnegative integer; 0 returns immediately. Each non-base call makes only two children and finite remaining work. Therefore both finite subtrees can finish. We are counting those actual calls, not extending the input contract.

Worked tree and timeline for split of 2

Give every invocation its own letter, even when its argument repeats. The letters name calls, not variables in the C program.

A is the initial split(2).
A’s first child is B, a split(1) call. B’s first and second children are C and D, each a separate split(0) call.
After B has fully returned, A’s second child is E, another split(1) call. E’s first and second children are F and G, each a separate split(0) call.

The tree contains seven nodes: A, B, C, D, E, F and G. Count a node once for each invocation. The longest root-to-base path contains three nodes, for example A, B, C. The words “path length” in this lesson mean the number of nodes, including both endpoints; that path has only two connecting edges.

Follow the actual entry and return order. Each list below gives the active frames from oldest to newest. An empty list means no split call remains active.

Enter A: active [A], total so far 1.
Enter B: active [A, B], total so far 2.
Enter C: active [A, B, C], total so far 3. This reaches the maximum active count of 3.
C returns 1: active [A, B], total stays 3. B now has left = 1.
Enter D: active [A, B, D], total so far 4.
D returns 1: active [A, B], total stays 4. B now has right = 1.
B returns 1 + 1 = 2: active [A], total stays 4. A now has left = 2.
Enter E: active [A, E], total so far 5. B, C and D have finished.
Enter F: active [A, E, F], total so far 6.
F returns 1: active [A, E], total stays 6. E now has left = 1.
Enter G: active [A, E, G], total so far 7.
G returns 1: active [A, E], total stays 7. E now has right = 1.
E returns 2: active [A], total stays 7. A now has right = 2.
A returns 2 + 2 = 4: active [], total stays 7.

The program prints 4, makes 7 total invocations, and reaches 3 active logical frames. Entry order is A, B, C, D, E, F, G; return order is C, D, B, F, G, E, A. There is no moment when both B and E are active: they are siblings executed one after the other.

A call tree contains all invocations over the run. The current logical stack contains only unfinished invocations on the route from the initial call to the current call. Drawing two branches beside each other does not mean they run at the same time.

Add whole subtrees but keep the longer active path

For a base call of split, both counts are 1. At a positive argument:

For total invocations, count this call once, then add every invocation in the first subtree and every invocation in the second subtree.
For maximum active frames, count this waiting caller once, then add the larger of the two child subtrees’ own maximum active counts. The child subtrees happen one after another, so do not add their peaks together.

For split(2), each child subtree has total 3 and peak 2. Therefore total = 1 + 3 + 3 = 7, while peak = 1 + max(2, 2) = 3. Here max is mathematical notation for the larger number; it is not a C function used by the program.

For the admitted inputs, a small check list is enough:

split(0): return 1; total 1; maximum active 1.
split(1): return 2; total 3; maximum active 2.
split(2): return 4; total 7; maximum active 3.
split(3): return 8; total 15; maximum active 4.
split(4): return 16; total 31; maximum active 5.

Repeated argument values do not collapse into one node: split(2) has four different base-case invocations at 0. Counting only the distinct arguments 2, 1, 0 would give 3, which happens to be the peak here but is not the total.

These exact finite counts are preparation for later analysis. This lesson does not teach full recurrence solving, asymptotic time or space complexity, machine-level stack measurement or complete branching-recursion coverage.

A precise analogy

Imagine a clerk processing work slips. Record every slip ever opened in a ledger. Keep a separate pile containing only the currently unfinished slips. A slip may ask for two smaller jobs, but the clerk finishes the first job and removes its slips before opening the second.

The ledger’s final count models total invocations. The tallest unfinished pile models maximum active logical frames. A result copied onto the waiting slip does not leave the completed child’s slip in the pile. This analogy models sequencing and bookkeeping; it does not prescribe physical storage or simultaneous execution by several clerks.

Key box for counting calls

Set the counting boundary first: this helper only; include initial and base calls; exclude main and library calls.
Give repeated invocations separate labels even if their arguments match.
Total calls = every node in the complete call tree.
Maximum active logical frames = most nodes on an active root-to-current-call path; for these helpers, a longest such path ends at a base call.
Waiting callers are active. Returned calls are finished. Keeping their result does not keep their frame active.
For sequenced child subtrees: add their totals; take the larger peak, then include the waiting caller.
Returned values, total calls and peak active frames are separate quantities.
Logical counts alone do not specify stack bytes or optimized machine storage.

Six original practice questions

Choose exactly one of the four options in each question. These are original learning exercises, not official previous-year questions or a full mock paper. Use each named helper exactly as defined. Unless a question asks about one specified instant, maximum active count means the maximum over the whole run. No question asks for physical stack depth or bytes.

Question 1

Using chain exactly as defined in the first worked program, what is (total chain invocations, maximum simultaneously active chain frames) for chain(0)? Include the initial and base-case invocation; exclude main and library calls.

A. (0, 0) B. (1, 1) C. (1, 0) D. (2, 2)

Question 2

Using the unchanged chain definition, which triple gives (returned value, total chain invocations, maximum active chain frames) for chain(4)? Use the lesson’s counting convention.

A. (9, 4, 4) B. (5, 5, 5) C. (9, 5, 1) D. (9, 5, 5)

Question 3

Using split exactly as shown, what is (total split invocations, maximum active split frames) for split(3)? Count every invocation, including all base cases.

A. (15, 4) B. (7, 3) C. (15, 15) D. (8, 4)

Question 4

In the worked split(2) trace, the root’s first child has fully returned and the root has stored left = 2. Its second child has not yet been entered. How many split frames are active at that exact point? This asks for the current count, not the maximum over the run.

A. 3 B. 4 C. 1 D. 7

Question 5

For this separate C11 program, starting n values are restricted to 0 through 4. During side_leaf(3), what is (total side_leaf invocations, maximum active side_leaf frames)? Both child statements run at every non-base call. Exclude main and library calls.

#include <stdio.h>

int side_leaf(int n) {
    if (n == 0) {
        return 1;
    }
    int first = side_leaf(n - 1);
    int second = side_leaf(0);
    return first + second;
}

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

A. (7, 3) B. (15, 4) C. (4, 4) D. (7, 4)

Question 6

Our source-level trace for split(3) has 15 total invocations and at most 4 active logical frames. Which conclusion is justified by these counts alone?

A. A compiler must store exactly four physical frames at the busiest moment. B. The trace counts calls and unfinished call records; exact machine storage and stack bytes need separate information. C. The function uses exactly 4 * sizeof(int) bytes of stack storage. D. All fifteen invocations execute at the same time.

Answers and option feedback

Answer 1: B

A. Incorrect. The initial invocation still enters the function and checks its base case. No child call does not mean no invocation.

B. Correct. There is exactly one invocation, which is both the initial call and a base-case call. It is active until it returns.

C. Incorrect. The single invocation is active while checking the guard and returning 1, so the maximum active count is also 1.

D. Incorrect. Initial call and base-case call describe the same invocation here. Do not count it twice.

Answer 2: D

A. Incorrect. The return value 9 is right, but arguments 4, 3, 2, 1 and 0 produce five invocations. This choice omits one endpoint.

B. Incorrect. The two call counts are right. The base returns 1 and each of four waiting callers adds 2, giving 9 rather than 5.

C. Incorrect. Waiting ancestors remain active. At the base case all five chain invocations are unfinished, even though only the base call is currently executing.

D. Correct. Returns from arguments 0 through 4 are 1, 3, 5, 7 and 9. The single path has five nodes, so total and maximum active counts are both 5.

Answer 3: A

A. Correct. The tree levels contain 1, 2, 4 and 8 invocations, giving 15 total. A longest active path has arguments 3, 2, 1, 0, giving 4 frames.

B. Incorrect. These are the counts for split(2). The extra tree level in split(3) contributes eight nodes, increasing the total from 7 to 15; the longest path grows from three nodes to four.

C. Incorrect. Total invocations are 15, but completed sibling subtrees do not remain active. Only one root-to-current-call path is active at a time.

D. Incorrect. Eight counts only the base-case leaves, which also sum to the returned value here. The seven non-base invocations must be included too.

Answer 4: C

A. Incorrect. Three is the maximum active count reached while a base call runs. The first child’s entire subtree has already returned at the stated point.

B. Incorrect. Four invocations have been entered so far: the root and the three in its first subtree. Three of those have already finished.

C. Correct. Only the root is unfinished. Its local left stores a returned integer; keeping that value does not keep the finished child’s frame active.

D. Incorrect. Seven is the total number of invocations for the whole run. The second subtree has not started, and completed calls are not active.

Answer 5: D

A. Incorrect. Seven is the correct total. The longest path is 3, 2, 1, 0, which has four nodes; three counts its connecting edges.

B. Incorrect. The second child always receives 0 and immediately returns. It does not grow into another n - 1 subtree, as it would in split.

C. Incorrect. Four is the maximum active count and also the returned value here. For total calls, add the three separate second-child invocations made at n = 1, 2 and 3 to the four-node first-child path.

D. Correct. The first-child path contributes arguments 3, 2, 1, 0; each of the three positive calls also makes a separate base call at 0. Total is 4 + 3 = 7, and the longest active path has 4 frames.

Answer 6: B

A. Incorrect. Logical frames describe the source-level execution model. An implementation may transform the code while preserving required behavior; the count does not prescribe physical records.

B. Correct. The two counts answer logical questions about this trace. They do not specify compiler optimization, frame layout, exact stack bytes or a safe general input limit.

C. Incorrect. sizeof(int) describes one int object’s size, not an entire call frame. The logical count alone cannot establish any such exact storage formula.

D. Incorrect. The child calls are sequenced, and waiting callers are active without executing their next statement. A total over the run is not a count of concurrent executions.

ParikshaPDF Editorial Team · Updated 13 Oct 2026