What is recursion?
Recursion is when a function calls itself to solve a smaller version of the same problem. Every recursive solution needs a base case that stops the calls, and a recursive case that moves toward that base case. Without a base case the function would call itself forever and crash with a stack overflow.
- Recursion is when a function calls itself on a smaller version of the same problem.
- Every recursion needs a base case to stop and a recursive case that moves toward it.
- Each call uses stack memory, so very deep recursion can cause a stack overflow.
The two parts every recursion needs
- Base case: the simplest input where the answer is known and no more calls happen.
- Recursive case: the function calls itself on a smaller input to build the answer.
int factorial(int n) {
if (n <= 1) // base case
return 1;
return n * factorial(n - 1); // recursive case
}
factorial(4); // 24int factorial(int n) {
if (n <= 1) // base case
return 1;
return n * factorial(n - 1); // recursive case
}
factorial(4); // 24def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case
factorial(4) # 24Each call waits on the call below it. The computer keeps track of these paused calls on the call stack, which is why very deep recursion can run out of memory.
Always mention the base case first, because a missing base case is the most common bug. If asked about the downside, say recursion uses stack memory for each call and can hit a stack overflow, and that many recursions can be rewritten as loops.
Frequently asked questions
What is the difference between recursion and iteration?
Recursion solves a problem by calling itself and uses the call stack, while iteration uses loops and constant extra space. Many recursions can be rewritten as loops.
What is tail recursion?
Tail recursion is when the recursive call is the last action in the function. Some languages optimise it into a loop so it does not grow the call stack.
Common follow up questions
Related interview questions
Want the full DSA guide?
Read every DSA concept with notes, diagrams, and code in one place. Track your progress as you go.
Open the DSA guide All DSA questions