Recursion: base case and call stack

One function, several unfinished calls

Before continuing, you should be able to trace if, integer expressions and ordinary function calls, and distinguish a copied int parameter from its caller’s variable. Read Functions, copied arguments and local state first. Arrays and pointers are not needed here.

By the end, you should be able to identify a base case, explain why the shown recursive calls reach it, and trace separate call records through their return values. This is an introduction to direct recursion with one recursive call per non-base invocation. It does not complete recursion, data structures or GATE CS.

Our code contract

We use C11, initialized ordinary automatic int objects and small representable results. For sum_to, use starting integers from 0 through 6 only. Other examples state their inputs explicitly. There are no static locals, global variables or shared pointer targets in these examples. Do not infer that every possible signed integer is a safe input, or that arbitrary recursion depth is supported.

Predict the two numbers printed by this program. Does the caller’s n become zero?

#include <stdio.h>

int sum_to(int n) {
    if (n == 0) {
        return 0;
    }
    int smaller = sum_to(n - 1);
    return n + smaller;
}

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

A recursive function calls itself, directly here through sum_to(n - 1). Each invocation has its own ordinary parameter n. The expression n - 1 computes an argument; it does not assign a new value to the caller’s n.

The base case is the route that returns without another recursive call. Here n == 0 returns 0. The recursive case first asks a smaller instance for a value and then adds this call’s own n. The initial value for smaller is not ready until the child call returns. Never read it as an already computed zero.

Worked trace Follow the calls down and the values back

Start with main: n = 3; the initialization of answer is waiting.

Returning 0 at the deepest call does not end all callers. It ends that one invocation and supplies the value needed by its immediate caller. Each waiting addition then finishes in reverse call order. The helper does not print; printf in main prints the final line.

What the call stack records

For tracing, keep a stack of active call records, or frames. A frame holds this invocation’s relevant parameters and locals, and where execution will resume. When a child runs, its caller is still active but waiting. The most recently entered unfinished call must finish before its waiting caller can continue: last in, first out.

Just before sum_to(0) returns, read the logical stack from oldest to newest:

sum_to(3) → sum_to(2) → sum_to(1) → sum_to(0)

There are four active sum_to calls, including the base-case call. For this straight chain there are also four total sum_to invocations. Exclude main and library calls from both counts. Total invocations and maximum active invocations are different measures; their equality here is not a rule for branching recursion.

This is a model of program execution, not a promise of a particular physical memory layout or an exact stack-byte count. A compiler may transform the implementation while preserving the program’s required behavior. Very deep recursion can exhaust implementation resources; the small examples do not establish a safe general depth limit.

Why this base case is reached

For the allowed sum_to inputs, n begins nonnegative. Whenever n > 0, the next argument is n - 1, a smaller nonnegative integer. After finitely many such reductions it is 0, where no recursive call is made. The starting boundary sum_to(0) makes one invocation and returns 0 immediately.

Both facts matter: a stopping case exists, and the recursive step approaches it within the stated input domain. If you start this same code at -1, repeatedly subtracting 1 will not reach 0. Such an input is outside our contract. Do not claim a predictable numeric result: actual execution can fail from resource exhaustion or eventually encounter invalid signed arithmetic. Likewise, replacing n - 1 with n would not make progress for a positive input.

A precise analogy

Imagine a stack of task cards. The card marked 3 says, “Wait for the result from card 2, then add my 3.” Card 2 waits for card 1; card 1 waits for card 0. Card 0 already has the answer 0. Finish the newest card, carry its answer to the card immediately beneath it, and continue.

Each card keeps its own number. Writing 0 on the newest card does not erase 3 on the oldest. The cards model separate state and pending work; they do not claim that C must physically allocate paper-like records, or that recursive calls run simultaneously.

Key box Read before the practice

• Base case: returns without another recursive call on that route.
• Progress: the next argument must approach a base case for the admitted inputs.
• New invocation: a new ordinary parameter and separate ordinary automatic locals.
• Waiting caller: keeps its own state and resumes only after the child returns.
• return: supplies one call’s result; it does not automatically print or finish all ancestors.
• Count rule here: include the initial and base-case calls; exclude main and library calls.
• Scope: small, direct, single-child recursion only; no branching-recursion analysis, recurrence solving or complete C coverage.

Six original practice questions

Choose exactly one option for every question. Every question has four options. These are original learning exercises, not official previous-year questions or a full exam mock. Try a call-and-return trace before reading the answers.

In question 4, void means that walk returns no value. The statement return; ends its current call. printf before the recursive call runs during entry; the one after it runs when that call resumes. Question 6 is a code-completion fragment, not a compilable program until the condition is supplied.

Question 1

Use the first worked program exactly as written. What does it print?

A. 0 6 B. 3 6 C. 3 3 D. 0 0

Question 2

Call sum_to(0). Which pair gives (returned value, total sum_to invocations), including the initial invocation?

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

Question 3

For sum_to(4), what is the maximum number of simultaneously active sum_to calls in our logical trace? Include the initial and base-case calls; exclude main and library calls.

A. 1 B. 4 C. 10 D. 5

Question 4

What sequence of numbers does this program print? Ignore the final space.

#include <stdio.h>

void walk(int n) {
    if (n == 0) {
        return;
    }
    printf("%d ", n);
    walk(n - 1);
    printf("%d ", n);
}

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

A. 2 1 1 2 B. 2 1 0 1 2 C. 1 2 2 1 D. 2 2 1 1

Question 5

What does this program print? Keep each call’s x separate.

#include <stdio.h>

int layers(int n) {
    int x = 10;
    if (n == 0) {
        return x;
    }
    int below = layers(n - 1);
    x = x + n;
    return x + below;
}

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

A. 12 B. 30 C. 33 D. 36

Question 6

For each starting input from 0 through 6, steps must count how many subtractions of 2 are needed to reach a non-positive value. It must return 0 immediately whenever its current n is non-positive. Which condition correctly fills the blank?

int steps(int n) {
    if (CONDITION) {
        return 0;
    }
    int rest = steps(n - 2);
    return 1 + rest;
}

A. n == 0 B. n <= 0 C. n == 1 D. n < 0

Answers and wrong-turn feedback

Answer 1: B

B is correct. The returned values are 0, 1, 3 and 6, while main keeps its own n = 3. A wrongly changes the caller’s n. C stops at an intermediate sum. D both changes the caller and discards the pending additions.

Answer 2: C

C is correct: the initial call exists, tests n == 0 and returns 0 without a recursive call. A omits the initial invocation. B invents a returned 1. D makes both errors. A base case is still an invocation.

Answer 3: D

D is correct. Just before the n = 0 call returns, the active parameters are 4, 3, 2, 1 and 0: five calls. A counts only the currently executing call. B omits the base-case call. C is the returned sum, not a call count. This is a logical count, not measured machine-stack space.

Answer 4: A

A is correct. The first printf runs on entry for n = 2, then n = 1. At n = 0, return ends that call before either print. The waiting n = 1 call prints 1; then n = 2 prints 2. B prints the base-case zero that the code skips. C reverses the descent. D finishes the outer call before its child, contrary to statement order.

Answer 5: C

C is correct. The n = 0 call initializes its own x = 10 and returns 10. The n = 1 call retains its own x = 10, changes it to 11 and returns 11 + 10 = 21. The n = 2 call changes its own x from 10 to 12 and returns 12 + 21 = 33. A omits returned child values. B ignores x = x + n in non-base calls. D incorrectly uses the outer call’s 12 in all three calls.

Answer 6: B

B is correct. For steps(3), parameters are 3, 1 and -1, so the answer is 2. For steps(0), it returns 0 immediately. A misses zero on an odd starting input. C does not stop at zero and also returns too early at 1. D takes one unnecessary step when n is zero; for example steps(0) would return 1. Do not execute the A variant on odd inputs or the C variant on even inputs: those cases miss their stopping condition and are not valid finite-output exercises. D does terminate on the stated inputs, but it overcounts even inputs by one.

Before moving on

If you changed the caller’s n, revisit copied arguments. If you stopped at the deepest return, draw the pending additions again. If you missed the base-case invocation, write one row for every entry, including zero. If you confused output order, mark each printf before or after the recursive call.

Next, practice recursive helpers on explicitly bounded arrays. Learn branching recursion and formal resource analysis in later lessons; success on these six questions does not establish mastery of them.

Source and scope note

The current official GATE 2027 CS syllabus, checked 13 October 2026, includes recursion in Programming and Data Structures. This source establishes topic relevance only. The examples, analogy, questions and explanations here are original teaching material. C11 is our stated teaching convention, not a claimed exam-language-version rule. This lesson does not change the year or identity of any existing course.