1. Introduction
Recursion is a technique in which a function calls itself, directly or indirectly, to solve a problem by breaking it down into smaller instances of the same problem. In C, any function can call itself as long as it eventually reaches a stopping condition. Recursive solutions are common for problems with a naturally repetitive, self-similar structure, such as computing factorials, Fibonacci numbers, traversing tree-like data structures, and implementing divide-and-conquer algorithms like merge sort and quick sort.
Cricket analogy: Recursion is like a coach breaking down "how India won the 2011 World Cup" into "how they won the semifinal" plus "how they won one final match," repeating until reaching the simplest case of a single ball bowled — used for tree-like problems like tournament bracket analysis.
Every recursive function must have two essential parts: a base case, which is the simplest instance of the problem that can be answered directly without further recursion, and a recursive case, which breaks the problem into a smaller sub-problem and calls the function again to solve it. Without a correctly reached base case, a recursive function calls itself indefinitely, eventually exhausting the program's memory.
Cricket analogy: The base case is like reaching the final ball of a Super Over that ends the match outright with no more play needed, and the recursive case is like each earlier over setting up the next one; skip the base case and you get a match that never ends, exhausting the stadium's time slot.
2. Syntax
returnType functionName(parameters) {
if (baseCondition) {
return baseResult; /* base case: stops recursion */
} else {
return someExpression(functionName(smallerProblem)); /* recursive case */
}
}The recursive case must always move the problem closer to the base case (for example, by decreasing a number, shrinking an array bound, or moving toward an empty list); otherwise the recursion never terminates.
Cricket analogy: Just as a batsman's run count toward a century must strictly increase with every scoring shot to eventually reach 100, each recursive call must shrink the problem — like reducing overs remaining — toward the base case, or the "innings" of recursion never ends.
3. Explanation
3.1 Base Case and Recursive Case
Consider factorial: n! = n * (n-1)! for n > 0, and 0! = 1 by definition. Here, 0! = 1 is the base case (it needs no further recursive call), and n! = n * factorial(n-1) is the recursive case. Every recursive call must work on a smaller version of the original problem (n-1 instead of n) so the sequence of calls eventually reaches the base case rather than continuing forever.
Cricket analogy: Computing a batting milestone like "runs needed for a century" works like factorial: reaching 0 runs needed is the base case (century already scored), while needing n runs equals scoring 1 run plus needing n-1 more, each ball working toward the smaller remaining target.
3.2 How the Call Stack Works
Each time a function calls itself, the C runtime pushes a new stack frame onto the call stack. A stack frame stores that call's local variables, parameters, and the return address (where execution should resume once this call finishes). These frames pile up as recursive calls go deeper ('winding up'), and then, once the base case is reached, each frame is popped off the stack in reverse order as the calls return and their pending arithmetic completes ('unwinding'). This is why recursive functions can perform work both before the recursive call (going down) and after it (coming back up), by using the returned value.
Cricket analogy: Each recursive call is like a fielding substitution slip stacked on the umpire's clipboard, storing which player and position to restore; as substitutions wind up during a rain delay, they pile up, then unwind in reverse order as play resumes, restoring each fielder in turn.
3.3 Step-by-Step Trace: factorial(4)
Winding phase (calls pushed onto the stack, each waiting for the next call's result): factorial(4) calls factorial(3); factorial(3) calls factorial(2); factorial(2) calls factorial(1); factorial(1) calls factorial(0). factorial(0) is the base case and returns 1 immediately without calling itself again.
Cricket analogy: Tracing a winding call chain like reviewing "over 4" requires reviewing "over 3," which requires "over 2," then "over 1," then "over 0"; over 0, the base case, is simply the coin toss with no prior over to check, returning immediately.
Call stack grows (winding):
factorial(4)
-> factorial(3)
-> factorial(2)
-> factorial(1)
-> factorial(0) returns 1 [base case]
Call stack shrinks (unwinding), each frame multiplies by n:
factorial(1) = 1 * factorial(0) = 1 * 1 = 1
factorial(2) = 2 * factorial(1) = 2 * 1 = 2
factorial(3) = 3 * factorial(2) = 3 * 2 = 6
factorial(4) = 4 * factorial(3) = 4 * 6 = 24
Final result: factorial(4) = 24Notice that no multiplication happens until factorial(0) returns 1; only then does each pending frame perform its multiplication as control unwinds back up to factorial(4), producing the final answer 24.
Cricket analogy: No runs are tallied until the base over(0) confirms "no more balls," and only then does each pending over's score get added back up the chain during the unwind, producing the final match total, like the total 24 runs.
3.4 Stack Overflow Risk
The call stack has a limited, fixed size determined by the operating system and compiler settings. Every recursive call consumes additional stack memory for its frame. If a recursive function never reaches its base case (due to a missing or incorrect base condition, or an argument that never converges toward it), the stack keeps growing until it exceeds this limit, causing a stack overflow — typically crashing the program with a segmentation fault rather than raising a catchable C error.
Cricket analogy: The call stack is like a stadium's fixed seating capacity for substitute players on the bench; if a match keeps calling up substitutes without a proper "final sub" base case, the bench overflows past capacity, causing a chaotic abandonment rather than a clean rule-based stoppage.
A missing or unreachable base case is the most dangerous recursion bug. For example, int factorial(int n) { return n * factorial(n - 1); } has NO base case at all — it will recurse forever (or until n underflows into negative numbers and the program crashes with a stack overflow). Always verify that (1) a base case exists, and (2) every recursive call moves strictly toward it, before trusting a recursive function with real input.
Tip: When designing a recursive function, write the base case FIRST and verify it independently, then write the recursive case assuming smaller sub-problems already work correctly (this is called the 'recursive leap of faith'). For performance-sensitive code operating on large inputs, also consider whether an iterative (loop-based) version would avoid the stack-depth and function-call overhead that recursion introduces.
4. Example
#include <stdio.h>
/* Recursive factorial: n! */
long factorial(int n) {
if (n == 0) { /* base case */
return 1;
}
return n * factorial(n - 1); /* recursive case */
}
/* Recursive Fibonacci: nth term (0-indexed: 0, 1, 1, 2, 3, 5, ...) */
int fibonacci(int n) {
if (n == 0) return 0; /* base case 1 */
if (n == 1) return 1; /* base case 2 */
return fibonacci(n - 1) + fibonacci(n - 2); /* recursive case */
}
int main(void) {
int num = 4;
printf("factorial(%d) = %ld\n", num, factorial(num));
for (int i = 0; i <= 6; i++) {
printf("fibonacci(%d) = %d\n", i, fibonacci(i));
}
return 0;
}5. Output
factorial(4) = 24
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(3) = 2
fibonacci(4) = 3
fibonacci(5) = 5
fibonacci(6) = 86. Key Takeaways
- Every recursive function needs a base case (stops recursion) and a recursive case (reduces the problem and calls itself again).
- Each recursive call pushes a new stack frame holding its own local variables and parameters onto the call stack.
- Recursion has two phases: winding (calls stack up toward the base case) and unwinding (results combine as calls return).
- In factorial(4), the base case factorial(0)=1 is reached first, then multiplications happen while the stack unwinds: 1*1=1, 2*1=2, 3*2=6, 4*6=24.
- A missing or unreachable base case causes unbounded recursive calls, exhausting the stack and crashing with a stack overflow.
- Fibonacci with two base cases (n=0 and n=1) demonstrates that a recursive case can call itself more than once per invocation.
- Deeply recursive problems can often be rewritten iteratively with a loop to avoid stack-depth limits and call overhead.
Practice what you learned
1. What are the two essential parts of every correct recursive function?
2. In the recursive trace of factorial(4), what is returned by factorial(0)?
3. What structure does the C runtime use to manage each recursive function call?
4. What is the most likely consequence of a recursive function that never reaches its base case?
5. Which factorial() implementation below is INCORRECT and will cause infinite recursion?
Was this page helpful?
You May Also Like
Functions in C
Learn C functions: declaration vs definition, parameters, pass-by-value, return statements, and prototypes with examples.
Pointers in C
Learn C pointers with syntax, address-of and dereference operators, pointer arithmetic, and common pitfalls, with examples and output.
Stack Implementation in C
Master array-based stack implementation in C with push, pop, peek, overflow/underflow checks, and full working code.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics