Unit 1 · Foundation of DSA
Recursion
Learn recursion in DSA with base case, recursive case, call stack, examples, factorial program, and beginner-friendly explanation.
Introduction
Recursion is a programming technique where a function calls itself to solve a smaller version of the same problem.
A recursive solution keeps breaking the problem down until it reaches a simple stopping condition called the base case.
Recursion is widely used in trees, graphs, divide and conquer algorithms, backtracking, and dynamic programming.
factorial(4)
-> 4 * factorial(3)
-> 3 * factorial(2)
-> 2 * factorial(1)
-> 1
Why Recursion is Important
Natural for Trees
Tree problems often repeat the same logic on subtrees.
Cleaner Logic
Some problems become easier to express recursively.
Divide and Conquer
Merge sort and quick sort use recursive thinking.
Backtracking
Problems like permutations and N-Queens rely on recursion.
Table of Contents
What is Recursion?
Recursion happens when a function calls itself directly or indirectly.
Every recursive function must move toward a stopping condition. Without a stopping condition, recursion continues until the program crashes due to stack overflow.
Simple idea: Solve a big problem by solving a smaller version of the same problem.
Base Case and Recursive Case
A recursive function has two main parts: base case and recursive case.
- Base case: The condition where recursion stops.
- Recursive case: The part where the function calls itself with a smaller input.
- Progress: Each call should move closer to the base case.
Recursion and Call Stack
Each recursive call is stored in the call stack. When the base case is reached, function calls start returning one by one.
This is why recursion uses extra memory. The deeper the recursion, the more stack space is required.
- Function calls are pushed onto the stack.
- The base case starts the returning phase.
- Completed calls are popped from the stack.
When Should We Use Recursion?
Recursion is useful when a problem naturally contains smaller subproblems of the same type.
- Tree traversal.
- Graph DFS.
- Factorial and Fibonacci.
- Binary search.
- Merge sort and quick sort.
- Backtracking problems.
Recursion Terms
| Term | Meaning |
|---|---|
| Base Case | Stopping condition |
| Recursive Case | Function calls itself |
| Call Stack | Memory area that stores active function calls |
| Stack Overflow | Error caused by too many unresolved calls |
C Program Example
This program calculates factorial using recursion.
#include <stdio.h>
int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
}
return n * factorial(n - 1);
}
int main() {
printf("%d", factorial(5));
return 0;
}
Output:
120
Key Points
- Recursion means a function calls itself.
- Every recursive function needs a base case.
- Recursive calls use stack memory.
- Recursion is powerful for trees, graphs, divide and conquer, and backtracking.
Interview Tip
Before writing recursive code, write the base case and the smaller subproblem in plain English.
Common Beginner Mistakes
- Forgetting the base case.
- Not reducing the input toward the base case.
- Ignoring stack memory usage.
- Trying to trace recursion only mentally without drawing the call stack.
Quick Revision
- Base case stops recursion.
- Recursive case calls the function again.
- Call stack stores pending calls.
- Too much recursion can cause stack overflow.
Summary
Recursion solves a problem by repeatedly solving smaller versions of the same problem. It is a core DSA concept used in many advanced algorithms and data structures.
