Recursion: returned values and pending calculations

A returned value is the start of the caller’s remaining work

Read Recursion: base case and call stack first. You should already know that an ordinary parameter belongs to one invocation, and that the waiting caller resumes when its child returns. You also need integer arithmetic and if statements. Arrays and pointers are not required.

This lesson concentrates on unwinding: finishing the suspended computations as recursive calls return. You will keep the caller’s own values, apply the exact pending operation, and evaluate a later condition using the returned result. Choosing termination guards is covered separately. These small examples do not complete branching recursion or formal time/space analysis.

Code contract

We use C11 and initialized ordinary automatic int objects. Unless a question gives another range, starting inputs are integers from 0 through 4. The deepest argument is 0, every recursive call uses n - 1, and all shown results fit even the minimum required range of int. There are no static locals, global variables or shared pointer targets. No claim is made about arbitrary inputs or an implementation’s maximum recursion depth.

Predict the output. It is not simply the sum of the argument values.

#include <stdio.h>

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

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

The base case supplies 1. Every non-base call must wait for its child, double the returned number, then add its own n. At a waiting call, write 2 × [child result] + my n. Do not replace the missing result with the child’s argument.

Worked trace One pending operation per caller

In the n = 3 call, child ultimately holds 8, not 2. The number 2 was the argument sent to another invocation; 8 is the value that invocation computed and returned. Those roles are different. The n = 3 call keeps its own parameter 3 throughout.

Each int child = ... initialization completes only when its call expression has a value. It does not start with an implied zero. The base-case route returns before reaching that declaration. return supplies a result to the immediate caller; only the printf in main displays anything here.

Expand with parentheses before simplifying

For score(3), an exact expansion is:

2 * (2 * (2 * 1 + 1) + 2) + 3 = 19

The innermost 1 is the base result; the added 1, 2 and 3 belong to different callers. Adding all those numbers first and doubling just once would change the computation. The parentheses record which calculation depends on which returned value.

Subtraction makes the danger especially clear. Predict this separate program.

#include <stdio.h>

int difference(int n) {
    if (n == 0) {
        return 0;
    }
    int child = difference(n - 1);
    return n - child;
}

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

The calls descend with arguments 3, 2, 1, 0. During return, the results are:

• difference(0) = 0
• difference(1) = 1 - 0 = 1
• difference(2) = 2 - 1 = 1
• difference(3) = 3 - 1 = 2

So it prints 2. The expansion is 3 - (2 - (1 - 0)), not 3 - 2 - 1 - 0. A waiting caller subtracts the entire returned result, not every argument it saw on the way down. Subtraction cannot be freely regrouped.

A repeatable unwinding method

1. On entry, record this call’s argument and any initialized locals it will need later.
2. Mark the precise statement waiting for the child. Keep an empty result slot rather than inventing a value.
3. Finish the child. Put its returned value into the waiting call’s result slot.
4. Resume that caller’s next statement. Use its own parameter and locals, not the finished child’s parameter.
5. Evaluate any later condition now, using the state that actually exists. An executed return ends this invocation; it is not overwritten by a return in a later statement.
6. Send the computed value to the next waiting caller and repeat.

A function can return the child’s value unchanged, multiply it, subtract it, or choose a branch from it. There is no rule that each recursive caller must add 1, and no rule that a base case must return 0. The problem being computed determines those operations.

The call-stack picture remains a logical tracing model. These counts and records do not prescribe physical storage, compiler optimization or stack bytes. Every example here has a single recursive child per non-base invocation; none requires assumptions about the evaluation order of multiple recursive calls in one expression.

A precise analogy

Imagine a stack of calculation slips. Each slip has its own instruction, such as “double the result sent back from the next slip, then add my 3.” Until that result arrives, leave its box empty. When it arrives, finish this slip’s arithmetic and send the answer to the slip underneath.

A child’s input is the request written on its slip; its returned value is the completed answer sent back. Those need not be equal. The analogy models dependencies and preserved caller state. It does not mean real C implementations must store paper-like slips or that waiting callers execute concurrently.

Key box Keep the pending operation exact

• Argument: the value sent into a call. Returned value: the result computed by that call.
• A waiting caller preserves its own ordinary parameter and relevant automatic locals in these examples.
• Finish a child before completing the caller’s pending initialization and later statements.
• Keep parentheses: n - child is not a flat subtraction of all call arguments.
• A later branch can depend on the returned value, not just on the original argument.
• Base values and return operations come from the function’s contract; neither is universally 0 or +1.
• Scope: bounded single-child recursion and returned-value reasoning, not full recursion mastery.

Six original practice questions

Choose exactly one of four options for each question. These are original learning exercises, not official previous-year questions or a full exam mock. For questions 1 and 3, use the exact earlier definitions. Question 6 is a function fragment with a placeholder; fill the expression before compiling it as part of a program.

Question 1

Using score exactly as defined in the worked example, what value does score(4) return?

A. 38 B. 42 C. 23 D. 41

Question 2

What does this program print? Its admitted starting inputs are integers from 0 through 4.

#include <stdio.h>

int digits(int n) {
    if (n == 0) {
        return 0;
    }
    int child = digits(n - 1);
    return 10 * child + n;
}

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

A. 40 B. 10 C. 1234 D. 4321

Question 3

Using difference from the second worked example, what does difference(4) return?

A. 2 B. 10 C. -2 D. 4

Question 4

What does this program print? A return need not change the child’s result.

#include <stdio.h>

int carry(int n) {
    if (n == 0) {
        return 4;
    }
    int child = carry(n - 1);
    return child;
}

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

A. 16 B. 7 C. 0 D. 4

Question 5

What does this program print? Evaluate the child < 5 condition only after that call has received its child value.

#include <stdio.h>

int choose(int n) {
    if (n == 0) {
        return 2;
    }
    int child = choose(n - 1);
    if (child < 5) {
        return child + 3;
    }
    return child - 1;
}

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

A. 5 B. 4 C. 7 D. 2

Question 6

For starting integers from 0 through 6, odd_total(n) must return the sum of the first n positive odd integers. The next odd integer after the first n - 1 terms is 2 * n - 1. Which expression completes the function correctly for every admitted input?

int odd_total(int n) {
    if (n == 0) {
        return 0;
    }
    int child = odd_total(n - 1);
    return EXPRESSION;
}

A. child + (2 * n - 1) B. 2 * child + n C. n * (child + 1) D. child + n

Answers and wrong-turn feedback

Answer 1: B

B is correct. score(3) returns 19, so the waiting n = 4 call returns 2 * 19 + 4 = 42. A doubles 19 but omits this call’s 4. C adds 4 to 19 but omits doubling. D reuses the child’s n = 3 instead of the waiting caller’s n = 4.

Answer 2: C

C is correct. Returning from n = 0 through 4 gives 0, 1, 12, 123, 1234. Each caller multiplies the whole returned child value by 10, then adds its own n. A stops at 10 * 4. B adds the inputs without shifting the child value. D reads descending call arguments as the answer; no printf runs during those calls.

Answer 3: A

A is correct. The returns for n = 0, 1, 2, 3, 4 are 0, 1, 1, 2, 2. The last operation is 4 - difference(3) = 4 - 2. B adds all positive inputs instead of following subtraction. C comes from flattening the nested expression into 4 - 3 - 2 - 1 - 0. D ignores the returned child value.

Answer 4: D

D is correct. The base-case call returns 4; each of the three waiting callers returns that same value unchanged. A adds 4 once per invocation, but the code contains no such addition. B adds the initial n = 3, also absent from the code. C assumes a base case must return 0, which is false.

Answer 5: C

C is correct. The n = 0 call returns 2. At n = 1, child = 2 < 5, so return 5. At n = 2, child = 5 is not less than 5, so return 4. At n = 3, child = 4 < 5, so return 7. A stops after n = 1; B stops after n = 2; D returns the base value without the waiting work. The test uses child, not n.

Answer 6: A

A is correct. The child returns the sum of the first n - 1 positive odd integers; add exactly the missing term 2 * n - 1. The base case returns the empty sum 0. At n = 3, the correct result is 1 + 3 + 5 = 9. B instead produces 11, C produces 15 and D produces 6 at that input. Checking n = 1 alone would not distinguish the four candidates; all return 1 there.

Before moving on

If you substituted an argument for a returned value, use separate “sent” and “received” columns. If you changed a caller’s n to the base-case zero, restore one record per invocation. If subtraction went wrong, retain all parentheses until the innermost result is known. If a condition went wrong, write the actual child value beside the test before choosing the branch.

Next, apply these return-value traces to a bounded array helper with an explicit empty-prefix case. Branching recursion, recurrence solving and formal resource analysis belong in later lessons.

Source and scope note

The official GATE 2027 CS syllabus, verified 13 October 2026, includes recursion in Programming and Data Structures. This source establishes topic relevance only. The lesson, programs and questions are original teaching material; C11 is a teaching convention, not a claim about an official exam language version. No existing course year or identity is reassigned by this lesson.