DSA · Chapter 12 of 40
Recursion
A recursive function solves a problem by calling itself on a smaller input until it reaches a base case. Every recursion needs a base case that stops it and a recursive step that makes progress toward that base case.
Recursion is the natural tool for trees, graphs, divide and conquer, and backtracking.
Call stack
Each call is pushed on the stack and popped when it returns. Deep recursion can overflow the stack, so depth matters.
Recursion vs iteration
Anything recursive can be written iteratively, sometimes with an explicit stack. Recursion is usually clearer for tree-shaped problems.
Example 1 (python)
def fact(n):
if n <= 1:
return 1
return n * fact(n - 1)
print(fact(5))Output
120Base case n <= 1 stops the recursion.
Example 2 (python)
def fib(n, memo={}):
if n < 2:
return n
if n in memo:
return memo[n]
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
print(fib(30))Output
832040Memoising turns exponential recursion into linear time.
Key points
- Every recursion needs a base case.
- Recursion depth n costs O(n) stack space.
- Memoisation removes repeated subproblems.
- Tree and graph problems are naturally recursive.
💡 Note: State the base case out loud first — most recursion bugs are missing or wrong base cases.