Recursion in C++
In this lesson: Understand recursion in C++ — base case, call stack — with factorial and Fibonacci programs and output. In Hindi & English.
What is recursion?
Recursion is when a function calls itself. Instead of a loop, the function solves a big problem by handing a slightly smaller version of it to another copy of itself — until the problem is small enough to answer directly.
The base case
Every recursion needs a base case — the simplest input, answered without calling again. It is what stops the chain. The other part, the recursive case, calls the function on a smaller input.
1) Base case — when to stop. 2) Recursive case — call yourself on something smaller. Miss the base case and it never stops.
Example: factorial
Factorial: 5! = 5 × 4 × 3 × 2 × 1. Notice n! = n × (n-1)! — that is the recursion.
#include <iostream>
using namespace std;
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
int main() {
cout << factorial(5) << "\n";
return 0;
}
| Call | n | Base case? (n<=1) | Return karta hai |
|---|---|---|---|
| factorial(5) | 5 | nahi | 5 * factorial(4) |
| factorial(4) | 4 | nahi | 4 * factorial(3) |
| factorial(3) | 3 | nahi | 3 * factorial(2) |
| factorial(2) | 2 | nahi | 2 * factorial(1) |
| factorial(1) | 1 | haan | return 1 (yahin rukta hai) |
| Wapas jodte hue: 2*1=2 → 3*2=6 → 4*6=24 → 5*24 = 120 | |||
factorial(n) khud ko n-1 ke saath call karta hai jab tak n 1 na ho (base case). Base case pe 1 return hota hai, phir har call apna n guna karke wapas bhejti hai. 5! = 120.
120
Tracing the calls
It helps to see how the calls stack up and then unwind:
factorial(4) = 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * 1))
= 24The calls go down to the base case, then the answers multiply back up.
Example: Fibonacci
Each Fibonacci number is the sum of the previous two, with two base cases:
int fib(int n) {
if (n < 2) return n; // base: fib(0)=0, fib(1)=1
return fib(n - 1) + fib(n - 2); // recursive case
}
// fib(6) → 8This simple Fibonacci recalculates the same values many times, so it is slow for large n. A loop or memoisation is far faster there.
Recursion vs iteration
| Recursion | Iteration | |
|---|---|---|
| Uses | Function calls itself | Loops |
| Memory | Extra (call stack) | Less |
| Best for | Trees, divide & conquer | Counting, simple repetition |
Anything recursive can be written with a loop, and vice versa — pick whichever reads more clearly for the problem.
Common mistakes
- Forgetting the base case, causing infinite recursion and a stack overflow.
- A recursive call that does not move toward the base case.
- Using naive recursion for Fibonacci on large
n(very slow). - Forgetting to
returnthe recursive call's result.
Write a recursive function to sum numbers from 1 to n, and another to compute the power base^exp. For each, write down the base case first, then the recursive case.
Summary
- Recursion is a function calling itself on a smaller input.
- Every recursion needs a base case to stop, plus a recursive case.
- Factorial and Fibonacci are classic examples.
- Recursion uses stack memory; a missing base case causes stack overflow.
- Use recursion for naturally recursive problems; loops for simple repetition.
