Recursion
Solve a problem by solving smaller copies of it: base cases, the call stack, divide and conquer, and memoization as a first step to dynamic programming.
beginner40 min#recursion#call-stack#base-case#memoization#divide-and-conquer
Prerequisites: Stacks and Queues, How Computers Run Programs
Why it matters
Recursion is the natural way to process anything that contains smaller copies of itself: nested folders, JSON, expression trees, and the branching choices in puzzles. Trees, graph traversals, merge sort, quicksort, backtracking and dynamic programming all rest on it. If you can describe a problem as "do a little work, then solve a smaller version of the same problem", the code is often just a few lines.
Intuition
Russian nesting dolls: to count the dolls, open the outer one. If it is empty, the count is 1. Otherwise the count is 1 plus the count for the doll inside. You never need the whole plan; you only need to trust that the smaller call returns the right answer and then combine it with your own step.
Every recursive function has two parts:
- Base case: an input so small that the answer is immediate. Without it the function calls itself forever.
- Recursive case: reduce the input (strictly toward the base case), call yourself, and combine the result.
How it works
The call stack. Each call gets its own frame holding its parameters, local variables and where to return. Calls pile up until the base case answers, then frames pop off one by one as each caller finishes its combination step.
depth(3)
-> 1 + depth(2)
-> 1 + depth(1)
-> 1 + depth(0)
-> 0 base case returns
<- 1 + 0 = 1
<- 1 + 1 = 2
<- 1 + 2 = 3
At the deepest point of depth(3), four frames are waiting on the stack. The top frame answers first, then each one below it can finish.
The stack has finite size. Python's default limit is about 1000 frames (it raises a RecursionError) and JavaScript engines allow roughly ten thousand or so before a RangeError. Recursion depth, not just time, is a cost: depth(n) uses O(n) stack space.
The power(2, 30) call from the code below halves the exponent each time, so it stacks up only 6 frames. Each number in the cells is one frame's exponent; the rightmost cell is the top of the stack.
The stack grows while the exponent halves, then unwinds as each frame combines its half with its own step.
Divide and conquer. If each call halves the input (like power below, or merge sort), the depth is only O(log n) and the code is both short and fast.
Overlapping subproblems. A naive recursive Fibonacci recomputes the same values exponentially many times: fib(5) calls fib(3) twice, fib(2) three times, and so on, giving about 1.6^n calls. Memoization fixes this: store each result in a map keyed by the arguments, and return the stored answer on repeat calls. The calls drop from exponential to linear, because each distinct input is computed once. This is top-down dynamic programming, covered in its own lesson.
Here is that blow-up for fib(4), which makes 9 calls, and then the memoized version. Step through all four views.
Overlapping subproblems: the same fib(k) appears in many branches. Memoization prunes every repeat branch down to one cached lookup.
Recursion versus loops. Any recursion can be rewritten with a loop and an explicit stack. Prefer a loop when the recursion is simple tail-style repetition or when depth could be huge. Neither Python nor most JavaScript engines optimize tail calls, so do not rely on that.
| Operation | Time | Notes |
|---|---|---|
| Linear recursion (depth(n)) | O(n) time, O(n) stack | One call per level |
| Halving (power, binary search) | O(log n) | Depth is log n |
| Naive Fibonacci | O(2^n) roughly | Overlapping subproblems recomputed |
| Fibonacci with memoization | O(n) time, O(n) space | Each n solved once |
| Divide and conquer (merge sort) | O(n log n) | Two halves plus linear merge |
Code: nested sums, fast power, and memoization
def total(nested):
"""Sum a list that may contain lists, to any depth."""
result = 0
for item in nested:
if isinstance(item, list):
result += total(item) # smaller sub-problem
else:
result += item # base case: a plain number
return result
def power(base, exp):
if exp == 0: # base case
return 1
half = power(base, exp // 2) # halve the problem each call
return half * half if exp % 2 == 0 else half * half * base
calls = 0
def fib_slow(n):
global calls
calls += 1
return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)
def fib_memo(n, memo=None, counter=None):
memo = {} if memo is None else memo
counter = [0] if counter is None else counter
counter[0] += 1
if n < 2:
return n, counter[0]
if n not in memo:
a, _ = fib_memo(n - 1, memo, counter)
b, _ = fib_memo(n - 2, memo, counter)
memo[n] = a + b
return memo[n], counter[0]
def depth(n):
return 0 if n == 0 else 1 + depth(n - 1)
print(total([1, [2, [3, 4]], [], 5]))
print(power(2, 30), power(3, 5))
print(fib_slow(25), calls)
print(fib_memo(25))
print(depth(500))// Sum a list that may contain lists, to any depth.
function total(nested) {
let result = 0;
for (const item of nested) {
if (Array.isArray(item)) result += total(item); // smaller sub-problem
else result += item; // base case: a plain number
}
return result;
}
function power(base, exp) {
if (exp === 0) return 1; // base case
const half = power(base, Math.floor(exp / 2)); // halve the problem each call
return exp % 2 === 0 ? half * half : half * half * base;
}
let calls = 0;
function fibSlow(n) {
calls++;
return n < 2 ? n : fibSlow(n - 1) + fibSlow(n - 2);
}
function fibMemo(n, memo = new Map(), counter = [0]) {
counter[0]++;
if (n < 2) return [n, counter[0]];
if (!memo.has(n)) {
const [a] = fibMemo(n - 1, memo, counter);
const [b] = fibMemo(n - 2, memo, counter);
memo.set(n, a + b);
}
return [memo.get(n), counter[0]];
}
const depth = (n) => (n === 0 ? 0 : 1 + depth(n - 1));
console.log(total([1, [2, [3, 4]], [], 5]));
console.log(power(2, 30), power(3, 5));
console.log(fibSlow(25), calls);
console.log(`(${fibMemo(25).join(", ")})`);
console.log(depth(500));Both versions print:
15
1073741824 243
75025 242785
(75025, 49)
500
fib(25) is 75025. The naive version needed 242,785 calls to compute it, while the memoized version used only 49 (one call per value from 25 down to 0, plus the repeat calls that hit the stored answer immediately). power(2, 30) needs only 6 nested calls (exponents 30, 15, 7, 3, 1, 0) instead of 30 multiplications.
Common pitfalls
- Missing or unreachable base case: leads to infinite recursion and a stack overflow. Check empty inputs, zero, null.
- Not shrinking the problem: calling with the same arguments, or growing them, never terminates.
- Mutable default arguments (Python):
def f(x, memo={})shares one dict across all calls forever. UseNoneand create it inside, orfunctools.lru_cache. - Exponential blowup: two recursive calls on overlapping inputs need memoization.
- Deep recursion on big input: a linked list or skewed tree with 100,000 nodes can overflow the stack. Convert to a loop or an explicit stack.
- Forgetting to return the recursive result: the function runs but returns
Noneorundefined.
Practice
Sum of digits easy
Hint
What is the base case, and how do you peel off one digit?
Show solution
If n < 10 return n. Otherwise return n % 10 + sum_digits(n // 10). The depth equals the number of digits, so O(d) time and stack space.
Reverse a string recursively easy
Hint
Reverse the rest and put the first character at the end.
Show solution
If the string has at most one character, return it. Otherwise return reverse(s[1:]) + s[0]. It is O(n^2) in practice because of slicing and concatenation; a loop or index-based version is better, but this shows the pattern.
Generate all subsets medium
Hint
For each item you have two choices. How does the problem shrink?
Show solution
For item i, recurse twice: once without it and once with it added to the current subset. When i == n, record the subset. There are 2^n subsets, so O(n * 2^n) time. This is the template for backtracking.
Climbing stairs and its memoized form hard
Hint
To reach step n you came from step n - 1 or n - 2. Does this look like another famous sequence?
Show solution
ways(n) = ways(n - 1) + ways(n - 2) with ways(0) = ways(1) = 1. The naive version is exponential. Add a memo map to make it O(n) time and space, or keep only the last two values in a loop for O(1) space. Recognizing that this is Fibonacci in disguise is the point.
Interview questions
- What happens if there is no base case? Calls pile up until the stack overflows (
RecursionErrorin Python,RangeErrorin JavaScript). - How do you convert recursion into iteration? Use an explicit stack holding what the call frames held, or restructure into a loop if the recursion is linear.
- Why is naive Fibonacci exponential, and how do you fix it? It re-solves overlapping subproblems; memoize or build bottom-up.
- What is the space cost of recursion? At least the maximum call depth, even if you allocate nothing else.
Interviewers look for: naming the base case first, proving the input shrinks, stating time and stack space, and spotting overlapping subproblems before being asked.
Quick check
A recursive function halves its input each call and does O(1) other work. About how many calls happen for n = 1,000,000?
Finished this lesson?
Further resources
- Recursion (computer science) (Wikipedia) (article)
- Memoization (Wikipedia) (article)