C Reference ยท Functions and Scope
Recursion in C
Reference for recursion in C: base cases, recursive calls, call stack depth, mutual recursion, tail calls and when a loop is the better choice.
A recursive function calls itself, directly or through other functions. Every recursive function needs a base case that returns without recursing, and each recursive call must move closer to that base case. Without both, the calls never stop and the program runs out of stack space.
C allows recursion in any function, with no special keyword. Each call gets its own set of parameters and local variables on the call stack, so the calls do not interfere with each other. Recursion fits problems that are naturally self-similar: trees, divide and conquer, backtracking.
unsigned long factorial(unsigned n) { if (n <= 1) return 1; /* base case */ return n * factorial(n - 1); /* smaller problem */ }
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.
Syntax
Recursion has no syntax of its own. The pattern is:
result f(input) { if (/* simplest case */) { return /* direct answer */; } /* reduce the input */ return combine(f(smaller_input)); }
| Part | Description |
|---|---|
| Base case | A condition that returns without calling the function again. Every chain of calls must reach one. |
| Recursive case | Calls the function with a smaller or simpler argument. |
| Frame | The stack memory for one call: parameters, locals, return address. It lives until that call returns. |
Errors / undefined behavior: unbounded recursion overflows the stack, which usually crashes with a segmentation fault (SIGSEGV). The C standard does not define the stack size or what happens on overflow. Typical limits are a few megabytes (8 MB on many Linux systems, 1 MB on Windows), which allows tens of thousands of small frames.
Usage notes
- Depth, not total calls, uses the stack.
fib(30)makes over a million calls but is only 30 frames deep. A linked list of a million nodes walked recursively is a million frames deep and likely crashes. - Naive double recursion is slow.
fib(n)recomputes the same values; use a loop, memoization with an array, or dynamic programming. - Tail calls. When the recursive call is the last thing the function does (like
gcd), an optimizing compiler such as GCC at-O2often turns it into a jump. The C standard does not guarantee this, so never depend on it for correctness. - Mutual recursion needs a prior declaration of the function used first, as with
is_oddabove. - Loops are often better. If recursion is only counting, use
for. Reserve recursion for structures that branch: trees, graph searches, permutations, parsing. - Convert to an explicit stack (your own array) when depth can be large or unbounded and the input is not trusted.
- Integer overflow. Recursive results grow fast:
factorial(21)overflowsunsigned long long. Overflow of signed types is undefined. - Static and global state inside a recursive function is shared by all calls; use parameters for per-call state.
mainmay call itself in C (unlike C++), but this is almost never a good idea.