A recursive function calls itself, directly or indirectly, with a base case that stops the recursion and a recursive case that makes progress toward it. Each active call gets its own stack frame holding its local variables and return address; these frames stack up as calls nest deeper and unwind as they return. Some languages guarantee tail-call optimization — rewriting a tail-recursive call into a loop internally, using constant stack space — but the C standard makes no such guarantee. A compiler MAY perform this optimization at higher optimization levels, but code that depends on it is relying on an implementation detail, not a language guarantee.
A basic recursive function
Without the base case (n <= 1), this would recurse forever, consuming a new stack frame on every call until the stack overflows — every recursive function needs a base case that's actually guaranteed to be reached.
long factorial(int n) {
if (n <= 1) { // base case — stops the recursion
return 1;
}
return n * factorial(n - 1); // recursive case — makes progress toward the base case
}
printf("%ld\n", factorial(5)); // 120Tail recursion: not guaranteed to be optimized in C
This version is written in tail-call form (the recursive call is the very last operation), but unlike languages such as Scheme that mandate tail-call optimization, C's standard doesn't require it — a sufficiently large n can still overflow the stack, even though the same logic in a guaranteed-TCO language would run in constant stack space.
long factorialTail(int n, long accumulator) {
if (n <= 1) {
return accumulator;
}
return factorialTail(n - 1, n * accumulator); // tail call — but NOT guaranteed optimized
}
// factorialTail(1000000, 1) may still overflow the stack in C,
// depending entirely on the compiler and optimization level usedWhen an explicit loop is the safer choice
For code where the recursion depth genuinely could be large and unpredictable (processing arbitrary user input, for instance), converting to an explicit iterative loop with your own stack or accumulator variable sidesteps this risk entirely — recursion in C is best reserved for cases with a naturally small, bounded depth, like tree traversal of a reasonably balanced structure.