Recursion and Divide and Conquer
Think recursively: base cases, the call stack, why naive recursion can explode, and how splitting a problem into independent halves gives fast algorithms such as fast exponentiation and merge sort. Ends with the recurrences that predict the running time.
A problem that contains a smaller copy of itself
Suppose you need to know how many files sit inside a folder, including every subfolder. You could invent a clever scheme with counters and a to-do list. Or you could notice something simpler: the answer for a folder is the number of files directly inside it, plus the answer for each subfolder. The subfolder question is the same question, only on a smaller folder. Eventually you reach a folder with no subfolders, and there the answer is just a count.
That shape, a problem defined in terms of smaller versions of itself plus a case simple enough to answer directly, is recursion. It is not a trick for showing off. It is the natural description of anything nested: file systems, HTML documents, arithmetic expressions, family trees, and the maze you are searching.
Every correct recursive function has three parts, and checking them one by one is how you debug recursion without losing your mind.
A function that solves a problem by calling itself on a smaller instance of the same problem. It needs (1) a base case answered directly, (2) a recursive case that reduces the problem, and (3) guaranteed progress so every chain of calls reaches the base case.
What the computer actually does: the call stack
The mystery of recursion evaporates when you see the machinery. Each call to a function gets its own frame holding that call's arguments and local variables. Frames are stacked: a call pushes a new frame, a return pops it. The recursive call is not special. It is an ordinary call that happens to name the same function.
Trace factorial(4). The frames pile up on the way down, each waiting for its inner call to finish, until factorial(1) returns 1 without recursing. Then the stack unwinds, and each waiting frame multiplies and returns. The multiplications happen on the way back, which is why the order of the printed lines in the example below looks mirrored.
This also explains the most common failure. If the base case is missing or never reached, frames pile up until the stack runs out and the program dies (a RecursionError in Python, a stack overflow elsewhere). Depth is a real resource.
call factorial(4) waiting for factorial(3)
call factorial(3) waiting for factorial(2)
call factorial(2) waiting for factorial(1)
call factorial(1) base case -> returns 1
back in (2): 2 * 1 = 2
back in (3): 3 * 2 = 6
back in (4): 4 * 6 = 241def factorial(n, depth=0):2 pad = " " * depth3 print(pad + "enter factorial(" + str(n) + ")")4 if n <= 1: # base case5 print(pad + "base case, return 1")6 return 17 result = n * factorial(n - 1, depth + 1) # recursive case, n shrinks8 print(pad + "return " + str(result))9 return result1011print("answer:", factorial(4))1213def runaway(n):14 return runaway(n + 1) # progress goes the wrong way: no base case1516try:17 runaway(0)18except RecursionError:19 print("RecursionError: the stack ran out")
enter factorial(4)
enter factorial(3)
enter factorial(2)
enter factorial(1)
base case, return 1
return 2
return 6
return 24
answer: 24
RecursionError: the stack ran outWhen recursion explodes: overlapping subproblems
Recursion is elegant but not automatically efficient. The textbook example is Fibonacci, defined as fib(n) = fib(n-1) + fib(n-2). The code is a direct transcription of the definition, and it is dreadfully slow, because the two recursive calls repeat each other's work. fib(5) needs fib(4) and fib(3); fib(4) also needs fib(3); that fib(3) computes fib(2) again, and so on. The number of calls grows exponentially.
The cure is to remember answers you have already computed (memoization). The first call for a given n does the work and stores the result; every later call is a dictionary lookup. The same recursion now touches each value of n once, so the cost drops from exponential to linear. This is the doorway to dynamic programming, covered in its own lesson.
Whenever a recursive function calls itself twice (or more) on overlapping inputs, ask whether the same arguments can recur. If they can, either memoize or restructure the algorithm.
1calls = 023def fib_naive(n):4 global calls5 calls += 16 return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)78def fib_memo(n, cache=None):9 global calls10 calls += 111 if cache is None:12 cache = {}13 if n in cache:14 return cache[n]15 cache[n] = n if n < 2 else fib_memo(n - 1, cache) + fib_memo(n - 2, cache)16 return cache[n]1718for n in (10, 20, 25):19 calls = 020 value = fib_naive(n)21 naive_calls = calls22 calls = 023 fib_memo(n)24 print("n =", n, "value =", value, "| naive calls:", naive_calls, "| memoized calls:", calls)
n = 10 value = 55 | naive calls: 177 | memoized calls: 19 n = 20 value = 6765 | naive calls: 21891 | memoized calls: 39 n = 25 value = 75025 | naive calls: 242785 | memoized calls: 49
Divide and conquer: split, solve, combine
Divide and conquer is recursion with a specific, disciplined shape. You divide the problem into smaller subproblems of the same kind, conquer each one recursively (the base case handles tiny inputs), and combine the sub-answers into the answer for the whole. The crucial difference from the Fibonacci trap is that the subproblems are independent and non-overlapping: the left half of an array and the right half share nothing, so nothing is recomputed.
You have already met it. Merge sort divides by position, conquers each half, and does its real work in the combine step. Binary search divides, but conquers only one half and has nothing to combine. Quick sort does its work while dividing and has nothing to combine.
The skill is choosing a split that makes combining cheap. Consider raising a number to a power. The obvious loop multiplies n times. But x to the 8th is (x to the 4th) squared, and x to the 4th is (x squared) squared. Halving the exponent each time needs only about log2 n multiplications. When n is odd, take one extra factor of x out first. The combine step is a single multiplication.
1def power_slow(x, n):2 result, mults = 1, 03 for _ in range(n):4 result *= x5 mults += 16 return result, mults78def power_fast(x, n):9 if n == 0: # base case10 return 1, 011 half, m = power_fast(x, n // 2) # divide: solve a problem half the size12 if n % 2 == 0:13 return half * half, m + 1 # combine: one multiplication14 return half * half * x, m + 2 # odd exponent: one extra factor1516for n in (8, 15, 1000):17 slow, ms = power_slow(3, n)18 fast, mf = power_fast(3, n)19 print("n =", n, "same answer:", slow == fast, "| slow mults:", ms, "| fast mults:", mf)
n = 8 same answer: True | slow mults: 8 | fast mults: 5 n = 15 same answer: True | slow mults: 15 | fast mults: 8 n = 1000 same answer: True | slow mults: 1000 | fast mults: 16
Predicting the cost: recurrences
Because the structure is recursive, the running time is too. Write T(n) for the time on n items. Merge sort satisfies T(n) = 2 T(n/2) + n: two subproblems of half the size, plus n work to merge. Fast exponentiation satisfies T(n) = T(n/2) + 1. Picture the recursion tree: how many levels, how many nodes per level, and how much work per node. Add the levels up and you have the total.
Three shapes cover most algorithms you will meet. The table lists them. The pattern to remember is the tension between how fast the problem shrinks and how fast the number of subproblems grows.
Master theorem, informal version
Common divide-and-conquer recurrences
| Recurrence | Where it appears | Solution | Why |
|---|---|---|---|
| T(n) = T(n/2) + 1 | Binary search, fast power | O(log n) | One subproblem, constant work, log n halvings |
| T(n) = 2 T(n/2) + n | Merge sort | O(n log n) | Every level does n work, and there are log n levels |
| T(n) = 2 T(n/2) + 1 | Visiting every node of a balanced tree | O(n) | The leaves dominate: n leaves, total work proportional to n |
| T(n) = T(n-1) + n | Insertion sort, quick sort with a terrible pivot | O(n^2) | The problem barely shrinks, so there are n levels |
A checklist for writing a recursive solution
When a recursive solution will not come, work through these questions in order instead of staring at the code. What is the smallest input, and what is the answer there? That is your base case. Suppose someone hands you the correct answer for a smaller input. How would you build the answer for this one from it? That is the recursive case, and you are allowed to trust the recursive call without tracing it, which is the leap of faith that makes recursion manageable. Finally, check that every recursive call is strictly smaller so the base case is certain to be reached.
It also helps to know when not to recurse. A plain loop is clearer and cheaper for linear processes, and Python does not optimise tail calls, so deep linear recursion (a list of 100,000 items) will hit the recursion limit. Reach for recursion when the data is nested or the problem genuinely branches.
1def deep_sum(value):2 if isinstance(value, int): # base case: a plain number3 return value4 return sum(deep_sum(item) for item in value) # recursive case: a smaller list56data = [1, [2, 3], [[4], 5], [], [[[6]]]]7print(deep_sum(data))8print(deep_sum([]))9print(deep_sum(7))
21 0 7
Check your understanding
These questions ask you to predict and to diagnose, which is what recursion actually demands of you.
A recursive function `f(n)` returns `f(n) + 1` when `n > 0` and `0` when `n == 0`. What happens when you call `f(3)`?
Quick Syntax & Reference Sheet
| Concept / Rule | Syntax / Usage |
|---|---|
| Recursive template | def solve(problem):
if is_smallest(problem): return direct_answer
return combine(solve(smaller_part(problem))) |
| Divide and conquer | split -> solve each half recursively -> combine |
| Memoization in Python | from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n): ... |
| Recursion limit | import sys; sys.getrecursionlimit() # default about 1000 |
Common Pitfalls & Developer Mistakes
Writing the recursive case before deciding the base case
Why it happens: Without a clear stopping point the recursion never ends, or ends with the wrong value for tiny inputs such as the empty list.
Recursing on an input that is not strictly smaller
Why it happens: Off-by-one slices such as items[0:] or n instead of n - 1 keep the problem the same size.
Recomputing overlapping subproblems
Why it happens: Two calls on overlapping arguments multiply the work at every level.