Base case and recursive case; tracing calls on the stack

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• With #define SQ(x) x * x, what is SQ(1 + 2)? from Lesson 1.8
• What does p->x mean? from Lesson 1.6
• What does each function call push on the call stack, and when is it popped? from Lesson 1.3.3

1 · The Hook

🎣

You stand in a long line at a ticket counter and want to know your position, but you can only see the person in front of you. Ask them: “What is your position?” They ask the person in front of them, and so on, until the first person in the line says “1”. Then each answer comes back, one more each time. Nobody counted the whole line; everyone solved a slightly smaller version of the same question. That is recursion.

2 · Predict First

🤔

What does this print?

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

int main(void)
{
    f(3);
    printf("\n");
    return 0;
}

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Output

3 2 1

f(3) prints 3 and calls f(2), which prints 2 and calls f(1), which prints 1 and calls f(0). f(0) hits the stopping rule and returns at once; then every waiting call finishes.

A function that calls itself

A recursive function calls itself, each time with a smaller problem. Every recursive function needs two parts:

• a base case: a small input answered directly, with no further call;
• a recursive case: the answer built from a call on a smaller input, so that the inputs move towards the base case.

Each call has its own frame

Nothing special happens in memory: each recursive call is an ordinary call (Lesson 1.3.3) and pushes its own stack frame with its own copy of n. Calls of the same function do not share locals.

int sum(int n)
{
    if (n == 0)              /* base case */
        return 0;
    return n + sum(n - 1);   /* recursive case */
}

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

Output

10

Going down and coming back

Trace sum(4) as an expansion. The calls go down until the base case; then values come back up as each frame finishes its addition:

sum(4) = 4 + sum(3)
              = 3 + sum(2)
                    = 2 + sum(1)
                          = 1 + sum(0)
                                = 0            (base case)
                          = 1 + 0 = 1
                    = 2 + 1 = 3
              = 3 + 3 = 6
sum(4) = 4 + 6 = 10

When recursion goes wrong

Without a reachable base case (missing, or the input never gets smaller), the calls never stop: frames pile up until the stack runs out, a stack overflow. f(−1) in the countdown above would recurse forever because n never reaches 0.

How deep does it go?

The maximum number of frames of the function on the stack at once (its recursion depth) is the length of the longest chain of calls. sum(n) reaches depth n + 1 (n, n − 1, …, 0).

4 · Visual

The stack at the deepest moment of sum(4): five frames of sum, each with its own n. From here the frames pop one by one, returning 0, 1, 3, 6, 10.

Ticket-line picture of recursion:

 you   ->  "what is your position?"  -> person ahead -> ... -> first person
                                                                   |
 you = 1 + (answer of person ahead)  <- ... <- 2 <---------------- "1"   (base case)

Questions travel down to the base case; answers travel back up.

5 · Worked Examples

Example 1 Easy

What does this print?

int digits(int n)
{
    if (n < 10)
        return 1;
    return 1 + digits(n / 10);
}

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

Solution

digits(2027) = 1 + digits(202) = 1 + 1 + digits(20) = 1 + 1 + 1 + digits(2) = 4. A one-digit number is the base case.

Output

1 4 7

Example 2 Medium

What does sum(n) do for negative n, and how would you fix it?

Solution

sum(−1) calls sum(−2), sum(−3), …: n never reaches 0, so the calls never stop and the stack overflows. Fix the base case to if (n <= 0) return 0; so every input reaches it.

Example 3 GATE

What does this print, and what is the maximum depth of calls to f for f(7)?

int f(int n)
{
    if (n <= 1)
        return 1;
    return n * f(n - 2);
}

int main(void)
{
    printf("%d %d\n", f(7), f(6));
    return 0;
}

Solution

f(7) = 7 × f(5) = 7 × 5 × f(3) = 7 × 5 × 3 × f(1) = 105. f(6) = 6 × 4 × 2 × f(0) = 48. f(7) uses the chain 7, 5, 3, 1: depth 4.

Output

105 48

6 · GATE Traps

⚠️

• A recursive case must move towards the base case for every allowed input; otherwise the recursion never ends (stack overflow).
• Each call has its own copy of the parameters and locals.
• Work written after the recursive call runs on the way back up, in reverse order.
• Recursion depth counts frames on the stack at once, not total calls.
• Check what happens for the smallest inputs (0, 1, negatives) against the base case.

8 · Memory Hook

🧠

“Ask the person in front.” Every call asks a smaller copy of itself and waits; the first person in the line answers without asking anyone.

9 · Connect the Dots

Lesson 1.3.3 showed the call stack for different functions; recursion is the same machinery with one function. So far each call made at most one further call. Next lesson answers: what happens when a call makes two or more recursive calls, and how many calls does that produce in total?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markOutput

What does this print?

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

int main(void)
{
    f(3);
    printf("\n");
    return 0;
}

• (A) 0 1 2 3
• (B) 3 2 1 0
• (C) 1 2 3
• (D) 3 2 1

Q2NAT1 markReturn value

What does this print?

int g(int n)
{
    if (n == 1)
        return 2;
    return 2 * g(n - 1) + 1;
}

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

Numerical answer: ________

Q3MCQ1 markBase case

A recursive function has no reachable base case for an input. What happens?

• (A) Calls continue until the stack overflows
• (B) The compiler rejects it
• (C) It loops forever without using memory
• (D) It returns 0

Q4NAT2 marksDepth

For sum(n) from the lesson, how many frames of sum are on the stack at the deepest point of sum(6)?

Numerical answer: ________

Q5MSQ1 markRecursion

Which are true?

• (A) A recursive function must have a base case to terminate.
• (B) Statements after the recursive call run after it returns.
• (C) Every recursive call gets its own copy of the local variables.
• (D) Recursive calls share one copy of their parameters.

11 · Rule Card

• Recursive function = base case (no call) + recursive case (smaller input).
• Every input must eventually reach a base case, or the stack overflows.
• Each call has its own frame: own parameters and locals.
• Calls go down to the base case; results come back up.
• Depth = longest chain of active calls (sum(n): n + 1).

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

recursionrecursive functionbase caserecursive caserecursion depthunwinding (coming back up)

13 · Answer Vault