Recursion: following separate calls
Understand stopping cases, progress, separate local state, returned results, and the limits of recursive designs.
In this chapter9 sections
A function can solve a problem by asking another call to solve a smaller part. If the new call uses the same function, we call the design recursion. The central idea is a sequence of separate calls, each with its own work still to finish.
1. Start with a smaller question
To add the integers from one through three, we can say: three plus the sum from one through two. That smaller sum is two plus the sum through one. Eventually we reach zero, where there is no work left to add. Each answer lets an earlier call finish.
The method needs two parts. The base case answers a question directly. The recursive case reduces the remaining problem. Here zero is the base case, and subtracting one makes progress toward it. Writing a self-call without that reasoning does not establish termination.
2. Keep the first example bounded
This complete C17 example deliberately accepts only values zero through ten. The largest sum is 55, so every intermediate addition fits even the minimum standard range of unsigned int. The assertions document and check that demonstration contract in this test build. They are not a replacement for validating untrusted input.
#include <assert.h>
/* Contract: n is at most 10. */
static unsigned triangle(unsigned n)
{
assert(n <= 10U);
if (n == 0U) return 0U;
return n + triangle(n - 1U);
}
static unsigned triangle_loop(unsigned n)
{
assert(n <= 10U);
unsigned total = 0U;
for (unsigned i = 1U; i <= n; ++i) total += i;
return total;
}
int main(void)
{
for (unsigned n = 0U; n <= 10U; ++n) {
assert(triangle(n) == triangle_loop(n));
assert(triangle(n) == n * (n + 1U) / 2U);
}
return 0;
}
3. Read calls downward and answers upward
| Call | Calculation waiting for a result | Eventually returns |
|---|---|---|
triangle(3) | 3 + triangle(2) | 6 |
triangle(2) | 2 + triangle(1) | 3 |
triangle(1) | 1 + triangle(0) | 1 |
triangle(0) | — | 0 |
For triangle(3), the first call cannot finish its addition until triangle(2) returns. That call waits for triangle(1), which waits for triangle(0). Zero returns first. Then the pending additions finish with one, three, and six. Returning from one call resumes its caller; it does not restart the whole program.
Explore with a visual model
Follow recursive calls and returns
VISUAL MODEL
Choose a small input and follow triangle(n). See which call waits and which result lets its caller continue.
triangle adds the unsigned integers from 1 through n. Each invocation has its own n parameter.
if (n == 0U) return 0U;return n + triangle(n - 1U);
No call is in progress.
Ready to call triangle(3). No call has started yet.
The input is limited to 0–5, and every sum fits unsigned int. This follows source-level calls; storage layout and call optimisation are implementation details.
Read the complete trace
- Ready to call triangle(3). No call has started yet.
- Enter triangle(3). This call has its own parameter value 3.
- Enter triangle(2). This call has its own parameter value 2.
- Enter triangle(1). This call has its own parameter value 1.
- Enter triangle(0). This call has its own parameter value 0.
- triangle(0) reaches the stopping case and returns 0. No smaller call is needed.
- triangle(0) returned 0. Its caller triangle(1) can now compute 1 + 0 and return 1.
- triangle(1) returned 1. Its caller triangle(2) can now compute 2 + 1 and return 3.
- triangle(2) returned 3. Its caller triangle(3) can now compute 3 + 3 and return 6.
- All calls have finished. triangle(3) returned 6 to the original caller.
4. Each call has separate ordinary local state
Every invocation receives its own parameter value. Deeper calls do not overwrite the caller’s n. Ordinary automatic local objects also have separate instances for recursive entries. A static local object would instead be shared across calls under its storage-duration rules. That difference matters when adding a counter or cached result.
A stack of unfinished worksheets is a useful mental model: finish the newest question, then use its answer in the previous one. Real implementations commonly use a call stack. C does not require this exact physical arrangement, a fixed size per call, or unlimited recursion depth.
5. Choose recursion when the structure helps
Recursion fits problems with smaller subproblems, such as walking a tree. A simple linear sum is often clearer as a loop; both forms appear above so their state can be compared. Recursive functions can also call one another indirectly. The same need for progress, valid inputs, and a depth policy remains.
A stopping case does not by itself prevent arithmetic overflow or excessive work. A recursive Fibonacci demonstration can repeat the same subproblems many times. A tail-position call is not a portable promise that a compiler will remove call storage. Explain correctness, resource use, and implementation observations separately.
If a function calls itself with the same unchanged input, is a base-case branch enough to guarantee it finishes?
Read the explanation
No. The calls must reach the stopping case or another justified exit. With an unchanged non-base input, the same unfinished problem is repeated.
Primary references and further reading
- WG14 N1570 — public C11 draft: 6.2.4 and 6.5.2.2: local instances and recursive calls; stable foundations used for C17.
Before you move on
- A recursive design needs a stopping case and a justified reduction toward it.
- Each invocation has separate parameters and ordinary automatic local instances.
- Finite arithmetic, call depth, and repeated work still need explicit limits.
Keep these ideas separate
- Calling downward / Returning upward
- Smaller calls start before their waiting callers can use the returned results to finish.
Why does triangle(3) need triangle(2), and which result allows the first waiting addition to finish?
Optional: say it aloud or keep a note. You can continue whenever you are ready.Check your understanding
Optional. Answers are not saved or sent, and reading stays unrestricted.
Read the explanation for every choice
- Yes, the presence of the branch forces every call to reach it.
A branch that is never reached cannot stop the recursion.
- Yes, C guarantees unlimited call depth.
Resource use and call depth are not unlimited portable guarantees.
- No. The calls need justified progress toward a stopping condition and resource limits.
✓ Correct reasoning. A sound argument also considers valid inputs, arithmetic, depth, and repeated work.
C17
Ready for the next idea?
Mark this chapter as read whenever you feel ready.