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.
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.
def 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.
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