APRideAPRideMatch Board

// STUHUB · C++ DATA STRUCTURES

Recursion vs Iteration: Call-Stack Traces, Base Cases, and the Exam Bugs Between Them

What actually happens on the call stack when a recursive function runs: base cases that guarantee termination, frame-by-frame traces of factorial and sum-of-digits, tail calls, and the four bugs exams love to plant.

Introduction

Recursion is a function that calls itself; iteration is a loop. Both repeat work, but recursion pays for it with stack frames — one per active call — and exams probe exactly that trade. This note traces what really happens frame by frame, states the two conditions every correct recursion needs, shows when a loop is the honest rewrite, and catalogs the four planted bugs that appear in tracing questions.

The two conditions every recursion needs

A recursive definition is correct only when both conditions hold:

  1. A base case — at least one input that is solved without another recursive call. Without it, the recursion never stops.
  2. Progress toward it — every recursive call must move strictly closer to a base case (a smaller n, a shorter array, a deeper node in a finite tree).

factorial is the canonical pair:

  • Base case: fact(0) = 1 (no recursive call).
  • Progress: fact(n) calls fact(n - 1) — n shrinks by exactly 1 each level.

Break either condition and you get the same symptom: stack overflow (or undefined behavior when the stack outruns its bounds). Exams phrase this as "what is missing from this function?" — the answer is almost always a missing or unreachable base case, or a recursive call that does not shrink the input.

cpp
int fact(int n) {
    if (n <= 0) return 1;        // base case: stops the descent
    return n * fact(n - 1);      // progress: n-1 is strictly smaller
}

The call stack, traced frame by frame

Every function call pushes a stack frame: the caller's return address plus the callee's parameters and locals. Recursion is nothing mysterious — it just stacks frames of the same function. Trace sum_digits(452) (sum of decimal digits):

call sum_digits(452)   -> 452/10 = 45, needs sum_digits(45) + 2
  call sum_digits(45)  -> 45/10 = 4,  needs sum_digits(4) + 5
    call sum_digits(4) -> 4 < 10, BASE CASE, returns 4
  returns 4 + 5        = 9
returns 9 + 2          = 11

Three things exams test about this trace:

  • Depth: the number of frames on the stack at the deepest point (here 3). For sum_digits(n) it is the number of digits — i.e. ⌊log₁₀ n⌋ + 1.
  • Order of evaluation: the multiplications/additions happen on the way back up, after the base case returns. The work is deferred, not immediate.
  • Total work: each frame does O(1) work, so sum_digits is O(number of digits) — logarithmic in n.

This is also the honest explanation of why naive recursion can be wasteful: naive fib(n) makes exponentially many calls because it recomputes the same subproblems — the fix (memoization) turns the tree back into a line.

cpp
int sum_digits(int n) {
    if (n < 10) return n;          // base case: one digit left
    return sum_digits(n / 10) + n % 10;   // shrink: drop last digit
}

Recursion vs iteration: the real trade

Any recursion can be rewritten as a loop with an explicit stack; any loop can be rewritten as a tail recursion. The practical trade:

RecursionIteration
StateImplicit (call stack)Explicit (loop variables)
SpaceO(depth) framesO(1) usually
RiskStack overflow on deep inputOff-by-one loop bounds
Fits naturallyTrees, divide-and-conquer, backtrackingRunning aggregates, scanning

Iterative sum_digits keeps one accumulator and no frames — for a linear pattern like this, the loop is the cleaner tool. Recursion earns its keep when the data is recursive (trees, nested lists) or the algorithm splits the problem (merge sort, quicksort, binary search on segments). Rule of thumb: linear over a flat structure → loop; branching over a nested structure → recursion.

A special case worth knowing: a tail call is a recursive call whose result is returned directly, with no pending work after it (n * fact(n-1) is not tail — the multiplication is pending). Compilers can optimize tail calls into loops (tail-call optimization), but C++ does not guarantee it — do not rely on it in answers.

cpp
// iterative rewrite: one accumulator, zero extra frames
int sum_digits_iter(int n) {
    int sum = 0;
    while (n > 0) { sum += n % 10; n /= 10; }
    return sum;
}

The four planted bugs (and how each smells)

Bug 1 — missing base case. return n * fact(n - 1); with no if. Smell: never returns; stack overflow on any input.

Bug 2 — no progress. return n * fact(n); — calls itself with the same n. The base case exists but is never reached. Smell: overflow even though a base case is written.

Bug 3 — wrong direction. return n * fact(n + 1); — grows away from the base case. Same smell, opposite cause.

Bug 4 — shadowed/interrupted progress. The call shrinks the input but skips past or misses the base case's guard: if (n == 0) combined with a halving call f(n / 2) when n == 1 halts at 1 / 2 == 0... which actually lands on 0; but if (n == 1) combined with f(n - 2) jumps straight from 2 to 0 and never touches 1. Smell: works for odd inputs, dies for even ones (or vice versa) — the asymmetry is the tell.

Exam method for any of these: trace the first three calls with actual numbers. The bug shows up by call two or three; staring at the code without numbers rarely finds it.

Exercises with solutions

Work through each question before opening the solution below it.

Exercise 1

Trace fact(4) the way the machine does: list every frame pushed and popped, in order, and state the maximum stack depth.

Solution

Push fact(4) → push fact(3) → push fact(2) → push fact(1) → push fact(0) (base case, returns 1). Pop fact(0)=1 → fact(1) returns 1×1=1 → fact(2) returns 2×1=2 → fact(3) returns 3×2=6 → fact(4) returns 4×6=24. Maximum depth: 5 frames (fact(4) down to fact(0)). The multiplications happen entirely during the pops — nothing is computed until the base case is reached.

Exercise 2

How many stack frames (including the initial call) does sum_digits(90317) use at the deepest point, and what is the total number of function calls?

Solution

Frames at deepest point = number of digits + 1 initial? Count carefully: sum_digits(90317) → sum_digits(9031) → sum_digits(903) → sum_digits(90) → sum_digits(9, base case). That is 5 calls total, all 5 on the stack at the moment the base case runs. So depth = 5, total calls = 5 (each call happens exactly once — the chain is linear, not branching). Digit count = 5, confirming depth = number of digits.

Exercise 3

This function is planted with a bug. Identify it, state the symptom, and fix it: int bad_sum(int n) { if (n == 1) return 1; return n + bad_sum(n - 2); }

Solution

Bug 4 — interrupted progress: with n - 2, an even starting value descends 6 → 4 → 2 → 0 → -2 → ... and never hits the base case n == 1. Symptom: infinite recursion / stack overflow for even n; correct only for odd n. Two fixes: guard the parity — if (n <= 0) return 0; if (n == 1) return 1; with the same recursive call — or change the progress step to n - 1 if the intent is a plain sum 1..n.

Exercise 4

Rewrite fact so the recursive call is a tail call, and explain why the pending multiplication disappears.

Solution

Carry the accumulated product as a parameter: int fact_tail(int n, int acc) { if (n <= 0) return acc; return fact_tail(n - 1, n * acc); } — call as fact_tail(n, 1). The multiplication n * acc is evaluated before the call, so the call's result is returned directly with nothing pending: a true tail call. Under tail-call optimization the compiler reuses one frame, making the space O(1); but since C++ does not guarantee that optimization, an exam answer should still present the loop as the guaranteed-O(1) alternative.

Published and updated 2026-08-09 · DUOCODE TECHNOLOGY