Recursion
Recursion is a programming technique where a function calls itself to solve a problem by breaking it into smaller versions of the same problem.
The most important idea is:
A recursive function must have a stopping condition called the base case.
1. Simple Example
Let's print numbers from 5 down to 1.
Normal approach
#include <iostream> using namespace std; int main() { for (int i = 5; i >= 1; i--) { cout << i << " "; } return 0; }
Output:
5 4 3 2 1
Now let's do the same using recursion.
Recursive approach
#include <iostream> using namespace std; void countdown(int n) { if (n == 0) { return; // Base case } cout << n << " "; countdown(n - 1); // Recursive call } int main() { countdown(5); return 0; }
Output:
5 4 3 2 1
2. Two Important Parts of Recursion
Every recursive function generally has two parts:
① Base Case
The condition that stops recursion.
if (n == 0) { return; }
② Recursive Case
The function calls itself with a smaller/simpler problem.
countdown(n - 1);
So:
Recursive Function | ├── Base Case → Stop | └── Recursive Case → Call itself
3. How Recursion Works
Consider:
countdown(3);
The function executes:
countdown(3) | └── countdown(2) | └── countdown(1) | └── countdown(0) | └── STOP
The calls happen like this:
countdown(3) countdown(2) countdown(1) countdown(0)
When countdown(0) reaches the base case, the function starts returning.
countdown(0) returns ↓ countdown(1) returns ↓ countdown(2) returns ↓ countdown(3) returns
4. Recursion Uses the Stack
This is very important because we just studied Stack.
When a function is called, information about that function call is stored in the call stack.
For:
countdown(3);
the stack grows:
┌──────────────┐ │ countdown(1) │ ├──────────────┤ │ countdown(2) │ ├──────────────┤ │ countdown(3) │ └──────────────┘
Then when the base case is reached, calls are removed from the stack:
countdown(1) → return countdown(2) → return countdown(3) → return
Key connection
Recursion internally uses the call stack.
That's why recursion is directly related to the Stack topic we just studied.
5. Factorial Using Recursion
Factorial:
5! = 5 × 4 × 3 × 2 × 1
We can define it recursively:
5! = 5 × 4! 4! = 4 × 3! 3! = 3 × 2! 2! = 2 × 1! 1! = 1
C++ code
#include <iostream> using namespace std; int factorial(int n) { if (n == 0 || n == 1) { return 1; // Base case } return n * factorial(n - 1); } int main() { cout << factorial(5); return 0; }
Output:
120
Execution
factorial(5) = 5 * factorial(4) = 5 * 4 * factorial(3) = 5 * 4 * 3 * factorial(2) = 5 * 4 * 3 * 2 * factorial(1) = 5 * 4 * 3 * 2 * 1 = 120
6. Recursion Tree for Factorial
For:
factorial(4)
calls go down:
factorial(4) ↓ factorial(3) ↓ factorial(2) ↓ factorial(1) ↓ 1
Then values return upward:
1 ↑ 2 × 1 = 2 ↑ 3 × 2 = 6 ↑ 4 × 6 = 24
Final answer:
24
7. Sum of First N Numbers
Suppose:
1 + 2 + 3 + 4 + 5 = 15
We can define:
sum(n) = n + sum(n-1)
C++ code
int sum(int n) { if (n == 0) { return 0; } return n + sum(n - 1); }
For:
sum(5)
we get:
5 + sum(4) 4 + sum(3) 3 + sum(2) 2 + sum(1) 1 + sum(0)
Then:
sum(0) = 0 sum(1) = 1 sum(2) = 3 sum(3) = 6 sum(4) = 10 sum(5) = 15
8. Print Numbers 1 to N
Earlier we printed:
5 4 3 2 1
We can also print:
1 2 3 4 5
using recursion.
void printNumbers(int n) { if (n == 0) { return; } printNumbers(n - 1); cout << n << " "; }
For:
printNumbers(5);
The calls go down first:
printNumbers(5) ↓ printNumbers(4) ↓ printNumbers(3) ↓ printNumbers(2) ↓ printNumbers(1) ↓ printNumbers(0)
Then printing happens while returning:
1 2 3 4 5
Output:
1 2 3 4 5
This is an important recursion concept:
Code before the recursive call executes while going down; code after the recursive call executes while returning.
9. Reverse a String Using Recursion
Suppose:
"UDAY"
We want:
"YADU"
One approach:
#include <iostream> #include <string> using namespace std; void reverseString(string &s, int left, int right) { if (left >= right) { return; } swap(s[left], s[right]); reverseString(s, left + 1, right - 1); } int main() { string s = "UDAY"; reverseString(s, 0, s.length() - 1); cout << s; return 0; }
Output:
YADU
The idea is:
U D A Y ↑ ↑ swap Y D A U ↑ ↑ swap Y A D U
10. Check Palindrome Using Recursion
A palindrome reads the same forward and backward.
Examples:
MADAM LEVEL RADAR
We compare the first and last characters.
bool isPalindrome(string &s, int left, int right) { if (left >= right) { return true; } if (s[left] != s[right]) { return false; } return isPalindrome(s, left + 1, right - 1); }
For:
MADAM
comparisons:
M == M A == A D
Therefore:
true
11. Fibonacci Using Recursion
Fibonacci sequence:
0 1 1 2 3 5 8 13 21 ...
Definition:
F(n) = F(n-1) + F(n-2)
Base cases:
F(0) = 0 F(1) = 1
C++ code
int fibonacci(int n) { if (n == 0) { return 0; } if (n == 1) { return 1; } return fibonacci(n - 1) + fibonacci(n - 2); }
For:
fibonacci(5)
the calls form a tree:
F(5) / \ F(4) F(3) / \ / \ F(3) F(2) F(2) F(1) / \ F(2) F(1)
Notice something important:
The same values are calculated again and again.
That's why this simple recursive Fibonacci implementation is inefficient.
Complexity
Time: O(2^n) Space: O(n)
The space is O(n) because the deepest chain of recursive calls is about n.
Later, Dynamic Programming will teach us how to avoid these repeated calculations.
12. Recursion vs Iteration
Recursion
int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }
Iteration
int factorial(int n) { int result = 1; for (int i = 1; i <= n; i++) { result *= i; } return result; }
Both can solve the same problem.
| Recursion | Iteration |
|---|---|
| Function calls itself | Uses loops |
| Uses call stack | Usually less extra memory |
| Often easier for tree problems | Often simpler for straightforward loops |
| Can be elegant | Usually more memory efficient |
| Can cause stack overflow | Usually avoids recursive stack growth |
13. Time and Space Complexity
Consider:
void print(int n) { if (n == 0) return; cout << n << " "; print(n - 1); }
There are n function calls.
Therefore:
Time Complexity = O(n)
And because all recursive calls remain on the call stack until they return:
Space Complexity = O(n)
So:
Time → O(n) Space → O(n)
14. What Happens Without a Base Case?
This is dangerous:
void fun() { cout << "Hello"; fun(); }
There is no stopping condition.
The calls keep increasing:
fun() ↓ fun() ↓ fun() ↓ fun() ↓ fun() ↓ ...
Eventually the call stack becomes full.
This causes:
Stack Overflow
So always ask:
When should my recursion stop?
15. Types of Recursion
Direct Recursion
A function calls itself directly.
void fun() { fun(); }
Indirect Recursion
One function calls another, which eventually calls the first.
void A() { B(); } void B() { A(); }
Tail Recursion
The recursive call is the last operation.
void print(int n) { if (n == 0) return; cout << n; print(n - 1); }
The recursive call happens at the end.
16. When Is Recursion Useful?
Recursion becomes especially useful when a problem naturally contains smaller versions of itself.
Important applications:
🌳 Trees
Tree traversal is commonly written recursively.
10 / \ 5 20
🔍 Graphs
DFS can be implemented recursively.
🔄 Backtracking
Examples:
- N-Queens
- Sudoku
- Maze
- Permutations
- Combinations
⚡ Divide and Conquer
Examples:
- Merge Sort
- Quick Sort
- Binary Search
🧠 Dynamic Programming
Many DP problems can first be understood using recursion.
17. Common Recursion Problems
You should eventually be able to solve:
- Print
1 to N - Print
N to 1 - Sum of first N numbers
- Factorial
- Fibonacci
- Power of a number
- Reverse a string
- Check palindrome
- Sum of digits
- Count digits
- GCD using recursion
- Binary search recursively
- Generate subsequences
- Generate permutations
- Tower of Hanoi
The later problems connect recursion to backtracking, searching, trees, and divide-and-conquer.
18. The Most Important Recursion Pattern
When you see a recursion problem, think:
1. What is the smallest problem? ↓ 2. What is the BASE CASE? ↓ 3. How can I reduce the problem? ↓ 4. Call the function with the smaller problem.
For example, factorial:
Problem: factorial(n) Smallest problem: factorial(0) = 1 Reduce: factorial(n) = n × factorial(n-1)
So:
int factorial(int n) { // Base case if (n == 0) return 1; // Smaller problem return n * factorial(n - 1); }
🧠 Final Summary
Remember these 5 things:
Recursion = Function calling itself 1. Base Case ↓ Stops recursion 2. Recursive Case ↓ Function calls itself 3. Each call creates a stack frame 4. Calls go down → then return back up 5. Missing/incorrect base case → Stack Overflow
The connection with what you've already learned is important:
Stack ↓ Call Stack ↓ Recursion ↓ Backtracking ↓ Trees / Graphs ↓ Divide & Conquer ↓ Dynamic Programming