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

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.

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.

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:

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.

// 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.

Which C++ standard does this page assume?

Standard C++17. C++ began as C with Classes in 1979 and first shipped commercially in 1985; what a compiler flag actually selects today is one of the ISO revisions below, and the committee has published a new one every 3 years since 2011. Build these listings with -std=c++17 and they compile as written.

Common questions

Where can I check this against the language itself?

Nothing on this page outranks the standard or the library reference. When this page and one of these disagree, they are right and we want to know.

• cppreference — the C++ standard library referenceThe fastest correct answer for what a container or algorithm actually guarantees.
• isocpp.org — the Standard C++ FoundationThe FAQ and the core guidelines, written by the people who define the language.
• ISO/IEC JTC1/SC22/WG21 — the C++ standards committeeWorking drafts of the standard itself, free to read, when the wording is the question.
• GCC online documentationWhat -Wall, -Wextra and the sanitizers used on these listings actually check.
• Microsoft Learn — C++ language documentationThe MSVC view, for readers whose lab machines build with Visual Studio.

Related pages