Recursion
DSA · Beginner
Definition
Recursion is when a function calls itself on a smaller version of the problem until a base case stops it.
Trees, backtracking, divide-and-conquer and DP are all built on recursion.
Diagram
Flowchart
Example: Factorial
def fact(n):
return 1 if n <= 1 else n * fact(n - 1)
print(fact(5))Output: 120
Complexity
Depends on calls; uses O(depth) stack space
Key points
- Always have a base case
- Each call uses stack memory
- Memoization avoids repeated work
Interview questions
What causes stack overflow?
Missing or unreachable base case, or very deep recursion.
Recursion vs iteration?
Recursion is often clearer; iteration avoids call-stack overhead.