Functions That Call Themselves

Nothing in C's rules forbids a function from calling itself, and because every call gets fresh copies of its parameters and locals, the pass-by-value machinery makes such calls behave sanely: each one is a separate world. That is recursion, the standard technique for problems that contain smaller versions of themselves, a fixture of every exam, and the doorway to understanding the call stack.

The Two Mandatory Parts

A recursive function stands on two legs, and exams ask for their names:

  • The base case: an input answered directly, with no further calls. It is the exit.
  • The recursive case: answer the input in terms of the function applied to a smaller input.

Factorial is the canonical first example, because its mathematical definition is already recursive: 0! is 1 (base case), and n! is n times (n-1)! (recursive case).

The guard's n > 12 is chapter 2 keeping watch: 13! overflows a 32-bit int, and signed overflow is undefined behaviour, so the range check is correctness, not politeness.

Tracing a Call

The exam skill is writing out the expansion, and it doubles as the correct mental model:

factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * (1 * factorial(0))))
= 4 * (3 * (2 * (1 * 1)))
= 24

Calls descend until the base case answers, then the multiplications resolve on the way back up. Each pending call is waiting with its own n, four separate ns existing at once, which pass-by-value's fresh-copies rule makes unremarkable. The machine keeps those pending calls on the call stack, growing by one frame per call and shrinking as each returns; a recursion that never reaches its base case grows the stack until the program dies, the recursive edition of the infinite loop. Missing or unreachable base cases are the planted bug: factorial(n - 1) reaches 0 from any positive n, but a careless factorial(n - 2) from odd n skips it forever.

A Second Shape: Digits Again

Digit problems recurse naturally, since peeling one digit leaves a smaller number:

Base case: a single digit is its own sum. Recursive case: last digit plus the sum of the rest, % 10 and / 10 from chapter 3 doing the peeling. Fibonacci completes the exam trio, with its two recursive calls per step, and carries a real lesson: the naive version recomputes the same values exponentially many times, so past toy sizes a loop does the same job in linear time.

Recursion or a Loop?

Every recursion can be rewritten as a loop and vice versa; the choice is clarity and cost. Factorial and digit sums are honestly simpler as loops, and the loop versions spend no stack. Recursion earns its keep where the problem's structure genuinely nests, trees and nested data (which arrive with dynamic structures later), divide-and-conquer like a recursive binary search, or grammar-shaped input, and exams reward knowing both directions: write the recursive version on demand, and name the loop as the practical alternative for linear problems.

Key Takeaways

  • Recursion needs a base case that answers directly and a recursive case that shrinks the input toward it; know both names.
  • Every call holds fresh parameters and locals on its own stack frame; pending calls stack up and resolve in reverse.
  • Hand-trace expansions (the factorial ladder) for exams; the trace is also the debugging tool.
  • A base case that is missing or unreachable is the recursive infinite loop, ended by stack exhaustion; range-guard inputs, and remember 13! overflows int.
  • Linear problems read better as loops; recursion shines when the problem itself nests. Exams want the recursive factorial, digit sum, and Fibonacci on demand.