What is Recursion?
Learn recursion — base case, recursive case, the call stack and stack overflow — with a factorial example and common DSA interview questions and answers.
Expected Interview Answer
Recursion is a technique where a function solves a problem by calling itself on a smaller instance of the same problem, until it reaches a base case that stops the recursion.
Every recursive function needs two parts: a base case that returns directly without further recursion, and a recursive case that reduces the problem toward the base case. Each call is placed on the call stack, so recursion trades clarity for stack memory and risks a stack overflow if the base case is missing or the depth is too large. Problems with self-similar structure — trees, factorials, divide-and-conquer — are natural fits.
- Elegant for self-similar / tree-shaped problems
- Often mirrors the mathematical definition directly
- Enables divide-and-conquer algorithms
AI Mentor Explanation
Recursion is like a batting order collapse where each dismissed batter sends in the next, same instruction repeated, until the last man is out (the base case) and the innings ends. Each new batter is a smaller version of the same task — "score until out". Without a final batter to stop at, the process would never end. Recursion is exactly this: repeat the same step on a smaller case until a stopping condition halts it.
Step-by-Step Explanation
Step 1
Define the base case
The smallest input that returns directly without recursing.
Step 2
Define the recursive case
Call the function on a smaller input that moves toward the base case.
Step 3
Combine results
Use the returned value from the smaller call to build the answer.
Step 4
Mind the stack
Each call uses stack memory; deep recursion risks a stack overflow.
What Interviewer Expects
- Base case + recursive case as the two essential parts
- Awareness of the call stack and stack overflow
- A concrete example (factorial, tree traversal)
- When recursion beats iteration and vice versa
Common Mistakes
- Forgetting or mis-defining the base case (infinite recursion)
- Not reducing the problem toward the base case
- Ignoring stack-depth limits on large inputs
- Using recursion where simple iteration is clearer/cheaper
Best Answer (HR Friendly)
“Recursion is when a function calls itself to solve a smaller version of the same problem, stopping at a base case. It’s a clean way to handle problems that break into similar sub-problems, like navigating a tree — as long as you define the stopping condition.”
Code Example
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case
print(factorial(5)) # 120Follow-up Questions
- What is the difference between recursion and iteration?
- What is tail recursion and why does it matter?
- What causes a stack overflow?
- How would you convert a recursive function to an iterative one?
MCQ Practice
1. Every recursive function must have a?
The base case stops the recursion; without it, the calls never end.
2. Recursion primarily uses which memory structure?
Each recursive call is pushed onto the call stack until it returns.
3. Missing or wrong base case typically causes?
Without a reachable base case the recursion never terminates and overflows the stack.
Flash Cards
Two parts of recursion? — A base case (stops) and a recursive case (reduces toward the base).
Where do recursive calls live? — On the call stack — deep recursion can overflow it.
Natural fits for recursion? — Self-similar problems: trees, factorials, divide-and-conquer.
Missing base case →? — Infinite recursion → stack overflow.