Consider `gcd2(18, 30)`. It calls `gcd2(12, 18)`, then `gcd2(6, 12)`, then `gcd2(0, 6)`, which returns 6. A function that calls itself, directly or indirectly, is recursive. Every active call has its own parameters and local variables; an earlier call remains active while a later one runs. section 7.3
inline size_t gcd2(size_t a, size_t b) [[__unsequenced__]] { 1
assert(a <= b); 2
if (!a) return b; 3
size_t r = b % a; 4
return gcd2(r, a);
}
The `gcd2` listing shows both essential parts: `if (!a) return b` stops the calls, and `gcd2(b % a, a)` advances toward that case. For positive `a`, the remainder is smaller than `a`. The assertion requires the ordered inputs this helper expects; the separate `gcd` wrapper checks for positive inputs and orders them. section 7.3
TAKEAWAY: Identify a stopping condition and show that every recursive step makes progress toward it. Without both, calls can continue until call resources are exhausted. A compiler can sometimes replace unbounded recursive calls with a loop that allocates no storage per call, so a stack failure is not a reliable stopping mechanism. section 15.2.1 section 15.4
A direct translation of the Fibonacci recurrence uses `fib(n-1) + fib(n-2)` and returns 1 for its first two terms. It is short, but its call tree repeats computations: the given time recurrence grows approximately with a power of the golden ratio. A cache records computed terms and gives linear time instead. A second version carries two terms in a buffer, updating them as calls proceed. Recursive syntax alone therefore says little about the amount of work performed. section 7.3
/* Compute Fibonacci number n with the help of a cache that may
hold previously computed values. */
size_t fibCacheRec(size_t n, size_t cache[static n]) {
if (!cache[n-1]) {
cache[n-1]
= fibCacheRec(n-1, cache) + fibCacheRec(n-2, cache);
}
return cache[n-1];
}
size_t fibCache(size_t n) {
if (n+1 <= 3) return 1;
/* Set up a VLA to cache the values. */
#if __STDC_VERSION__ > 202311L
/* Since C23, VLA can be default initialized. */
size_t cache[n] = { };
#else
size_t cache[n]; memset(cache, 0, n*sizeof(*cache));
#endif
/* Non-trivial initialization is replaced by assignment. */
cache[0] = 1; cache[1] = 1;
/* Call the recursive function. */
return fibCacheRec(n, cache);
}
The cached Fibonacci listing makes the tradeoff concrete: an entry is computed recursively only when it has no stored value, then reused by later calls. Its wrapper prepares the cache before starting the recursion. section 7.3
Nesting as recursive descent
A recursive-descent parser handles text inside `{}` by descending when it encounters an opening brace and ascending at a closing brace. Its output replaces brace nesting with progressively deeper indentation. Unlike the arithmetic examples, it also checks whether nesting is too deep before proceeding. section 19.1
