← View series: problem solving with dsa
~/blog
Recursion
A function calls itself. The first time you see it, recursion looks circular and illegal. The second time, it looks like a clever trick. By the third or fourth time, it becomes a normal pattern — you see the self-similar structure in the problem and write the recursive solution without thinking about it.
The Structure
Every recursive function has two mandatory parts:
- Base case — the smallest version of the problem that you can solve directly.
- Recursive step — reduce the problem toward the base case and call yourself.
Without a base case, the function recurses forever (until stack overflow). Without a recursive step that reduces toward the base case, same result.
Manual trace — factorial(4) before any code, walk through what we want:
| Step | Call | n | Condition | Action |
|---|---|---|---|---|
| 1 | factorial(4) | 4 | n > 1 | returns 4 × factorial(3) |
| 2 | factorial(3) | 3 | n > 1 | returns 3 × factorial(2) |
| 3 | factorial(2) | 2 | n > 1 | returns 2 × factorial(1) |
| 4 | factorial(1) | 1 | n ≤ 1 | returns 1 — base case |
| 5 | factorial(2) | — | unwinding | returns 2 × 1 = 2 |
| 6 | factorial(3) | — | unwinding | returns 3 × 2 = 6 |
| 7 | factorial(4) | — | unwinding | returns 4 × 6 = 24 |
Two phases: the calls wind down until the base case is hit, then the results unwind back up. The code should match exactly that structure.
Example 1 — factorial.
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)Manual trace for factorial(4):
factorial(4) = 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * 1))
= 24
The calls build up a chain (depth 4), then the returns unwind it.
flowchart TD
A["factorial(4)"] --> B["factorial(3)"]
B --> C["factorial(2)"]
C --> D["factorial(1)\nbase case → 1"]
D -.->|"returns 1"| C
C -.->|"returns 2"| B
B -.->|"returns 6"| A
A -.->|"returns 24"| E(["result: 24"])Solid arrows are calls (going down).
Dotted arrows are returns (going back up).
The Call Stack
Every function call pushes a frame onto the call stack — return address, local variables, and parameters. Each recursive call adds another frame. When the base case returns, frames start popping in reverse order.
Example 2 — call stack for factorial(4).
Call stack builds:
factorial(1) — base case, returns 1
factorial(2) — waiting for factorial(1)
factorial(3) — waiting for factorial(2)
factorial(4) — waiting for factorial(3)
main
Call stack unwinds:
factorial(1) returns 1 → factorial(2) resumes
factorial(2) returns 2 → factorial(3) resumes
factorial(3) returns 6 → factorial(4) resumes
factorial(4) returns 24 → main resumes
Maximum recursion depth. Python's default recursion limit is 1000. factorial(1001) raises RecursionError. For deep recursion, use iteration or sys.setrecursionlimit().
Time: O(n). Space: O(n) for the call stack.
Example: Fibonacci
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)if n <= 1: return n — two base cases in one line. fib(0) returns 0, fib(1) returns 1. Both match the Fibonacci definition.
return fibonacci(n - 1) + fibonacci(n - 2) — each call branches into two subproblems. Unlike factorial (one recursive call per level), this creates a binary call tree. Every node spawns two children until a base case is reached.
Time: O(2^n) — without memoization. Each level doubles the number of calls. Space: O(n) — call stack depth.
When to Use Recursion
Recursion fits problems with self-similar structure:
- Tree and graph traversal — every subtree is a smaller tree.
- Divide-and-conquer algorithms — merge sort, quick sort, binary search.
- Backtracking — exploring decision trees (N-Queens, Sudoku).
- Dynamic programming — recursive formulation with memoization.
The dividing line: if the iterative version requires an explicit stack or queue (tree traversal, DFS), the recursive version is usually cleaner. If the iterative version is a simple loop (factorial, Fibonacci), recursion adds overhead with no readability gain.
Code Trace — factorial(4)
| Call | n | n <= 1? | Recursive call | Return value |
|---|---|---|---|---|
factorial(4) | 4 | No | 4 * factorial(3) | 24 |
factorial(3) | 3 | No | 3 * factorial(2) | 6 |
factorial(2) | 2 | No | 2 * factorial(1) | 2 |
factorial(1) | 1 | Yes | (base case) | 1 |
Code Trace — fibonacci(4) showing repeated subproblems
| Call | n | n <= 1? | Recursive calls | Return |
|---|---|---|---|---|
fib(4) | 4 | No | fib(3) + fib(2) | 3 |
fib(3) | 3 | No | fib(2) + fib(1) | 2 |
fib(2) #1 | 2 | No | fib(1) + fib(0) | 1 |
fib(2) #2 | 2 | No | fib(1) + fib(0) | 1 |
fib(1) | 1 | Yes | (base) | 1 |
fib(0) | 0 | Yes | (base) | 0 |
fib(2) appears twice in this small trace. For larger n, the waste grows exponentially.
Recursion vs Iteration
| Aspect | Recursion | Iteration |
|---|---|---|
| Stack usage | O(depth) call stack | O(1) explicit variables |
| Readability | Matches problem structure | May need manual stack |
| Performance | Function call overhead | Generally faster |
| Risk | Stack overflow | Infinite loop |
| Debugging | Harder — many frames | Easier — linear flow |
The choice is often stylistic for problems that support both. Tree traversal is impractical to write iteratively without a manual stack. Factorial is trivial either way. Fibonacci is better iteratively because the recursive version is exponential.
The memoized Fibonacci runs in O(n) — same as factorial. That shift from exponential to linear, by caching results you've already computed, is one of the most satisfying transformations in programming. The recursive structure stays intact; you just stop repeating work. That pattern — recursive thinking with iterative efficiency — shows up again in merge sort, dynamic programming, and tree traversal.