Know this before you start: “Recursion: base case and the call stack”
Recursion: the base case and the call stack
A recursive function solves a problem by calling itself on a smaller version. It needs a base case that stops, and every call waits on the call stack.
The idea
Recursion splits a problem into a smaller copy of itself plus a little work. factorial(n) = n × factorial(n − 1). Trust that the smaller call returns the right answer and only write how to combine it.
Every recursion needs a base case that answers directly without recursing (factorial(0) = 1), or it never stops.
Each call that's waiting sits on the call stack. Python allows about 1,000 nested calls by default, which matters for deep inputs.
See it step by step
factorial(3)
- factorial(3) waits for factorial(2), which waits for factorial(1), which waits for factorial(0).
- factorial(0) = 1: the base case.
- Unwinding: 1 × 1 = 1, 2 × 1 = 2, 3 × 2 = 6.
In code (Python)
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1)
def power_set_size(n):
return 1 if n == 0 else 2 * power_set_size(n - 1)
print(factorial(3), factorial(5)) # 6 120
print(power_set_size(4)) # 16Depends on the calls: factorial is O(n) time and O(n) stack space.
When you'll use it
- Trees, backtracking, divide and conquer, memoized DP: anything defined in terms of smaller copies.
Common mistakes
- No base case, or one that's never reached.
- Recomputing the same calls many times (fix with memoization).
