Unit 1 · Foundation of DSA
Common Mistakes in Recursion
Avoid common recursion mistakes in DSA, including missing base cases, wrong return values, infinite recursion, and stack overflow.
Introduction
Recursion is powerful, but small mistakes can make recursive programs fail badly.
Most recursion bugs come from missing base cases, incorrect parameter changes, wrong return handling, or misunderstanding the call stack.
This chapter focuses on those common mistakes so you can debug recursive code faster.
Bad Recursion
No base case or no progress
|
v
Infinite calls
|
v
Stack overflow
Why Recursion Bugs Happen
Hidden State
Each call has its own local variables.
Return Flow
Values are calculated while calls return.
Stack Usage
Too many calls can exhaust stack memory.
Base Case Logic
One wrong condition can break the whole solution.
Table of Contents
Mistake 1: Missing Base Case
A recursive function without a base case keeps calling itself forever.
Eventually, the call stack becomes full and the program may crash with stack overflow.
Fix: Always write the stopping condition before the recursive call.
Mistake 2: Not Moving Toward Base Case
Even with a base case, recursion fails if the input does not move closer to that base case.
- Wrong:
fact(n)callsfact(n)again. - Correct:
fact(n)callsfact(n - 1). - Each recursive call should reduce or simplify the problem.
Mistake 3: Wrong Return Value
Many recursive functions depend on returned values. If you forget to return the recursive result, the function may produce incorrect output.
- Use
return n * fact(n - 1);for factorial. - Use
return fib(n - 1) + fib(n - 2);for Fibonacci. - Do not call recursion without using its result when the result matters.
Mistake 4: Too Much Recursion
Some recursive solutions are correct but inefficient. Fibonacci using plain recursion repeats the same work many times.
For such cases, optimization techniques like memoization or iterative solutions are better.
- Plain Fibonacci recursion has exponential time.
- Deep recursion can use too much stack memory.
- Tail recursion or iteration may be more practical in some languages.
Common Recursion Mistakes and Fixes
| Mistake | Problem | Fix |
|---|---|---|
| No base case | Infinite recursion | Add stopping condition |
| No progress | Never reaches base case | Reduce input each call |
| Wrong return | Incorrect answer | Return recursive result |
| Too many repeated calls | Slow program | Use memoization or iteration |
C Program Example
This corrected factorial function has both a base case and progress toward that base case.
#include <stdio.h>
int fact(int n) {
if (n <= 1) {
return 1;
}
return n * fact(n - 1);
}
int main() {
printf("%d", fact(5));
return 0;
}
Output:
120
Key Points
- Every recursive function needs a base case.
- Each recursive call must move closer to the base case.
- Return values matter in many recursive functions.
- Deep or repeated recursion can cause performance problems.
Interview Tip
Debug recursion by printing the parameter value at the start of each call. It quickly shows whether the function is moving toward the base case.
Common Beginner Mistakes
- Writing the recursive call before checking the base case.
- Using the wrong comparison in the base condition.
- Assuming all recursive solutions are efficient.
- Forgetting that every call has separate local variables.
Quick Revision
- Base case prevents infinite recursion.
- Progress makes recursion reach the base case.
- Return flow builds the final answer.
- Repeated subproblems need optimization.
Summary
Most recursion errors are caused by missing stopping conditions, no progress toward the base case, wrong return handling, or inefficient repeated calls. Careful dry runs and call stack tracing make these bugs much easier to fix.
