🌀 Recursion in Programming — Base Case, Recursive Step and Examples
Master recursion in C++ — base case, recursive case, the call stack, and classic problems (factorial, Fibonacci, sum). Learn when to use it and when not to.
Recursion is when a function calls itself to solve a smaller version of the same problem.
🧠 The 2 ingredients
- Base case — a stopping condition where you return without recursing
- Recursive case — call yourself with a smaller / simpler input
📜 Classic: factorial
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
// factorial(5) = 120⚙️ How it works under the hood
Each call pushes a new stack frame. When the base case returns, frames pop one by one and combine results.
⚠️ Stack overflow
Too many recursive calls without a base case → the call stack overflows. Crash.
🧠 Recursion vs iteration
- Anything recursive can be rewritten as iterative (use an explicit stack)
- Recursion is elegant for tree/graph problems, divide-and-conquer, backtracking
- Iteration is usually faster (no call overhead) for simple loops
💻 Code Examples
Factorial — the canonical example
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
std::cout << factorial(5);Output:
120
Fibonacci — naive (slow)
int fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
std::cout << fib(7);Output:
13
Sum of array recursively
int sum(int arr[], int n) {
if (n == 0) return 0;
return arr[n-1] + sum(arr, n-1);
}
int nums[] = {1,2,3,4,5};
std::cout << sum(nums, 5);Output:
15
⚠️ Common Mistakes
- Forgetting the base case — infinite recursion → stack overflow → crash.
- Wrong base case condition (off-by-one).
- Calling with the same argument or larger — never converges to the base case.
- Using naive recursion for problems with overlapping subproblems (fib, knapsack) instead of memoization — exponential blowup.
🎯 Interview Questions
Real questions asked at top product and service-based companies.
Q1.What is recursion?Beginner
A function calling itself with a smaller/simpler version of the input. Each call must move toward a base case that returns without recursing.
Q2.What is the base case and why is it required?Beginner
The condition that ENDS the recursion and returns a direct answer. Without it, the function calls itself forever — the call stack fills up and the program crashes.
Q3.What is a stack overflow?Intermediate
Every function call uses memory on the call stack. Recursing too deeply exhausts the stack, causing a crash.
Q4.Can every recursive solution be written iteratively?Intermediate
Yes — using a loop and an explicit stack/queue data structure. The recursive form is often shorter; iteration is usually faster.
Q5.What is tail recursion?Advanced
When the recursive call is the LAST operation in the function. Some compilers optimize tail calls into loops (no extra stack frames). C++ does not guarantee tail-call optimization.
🧠 Quick Summary
- Recursion = function calls itself with smaller input.
- Always: base case + recursive case.
- Each call adds a stack frame; too deep = stack overflow.
- Great for tree/graph traversal, divide-and-conquer.
- Use memoization or DP for overlapping subproblems.