Problems that contain themselves
How many files are in a folder? You can't just count the files you see, because some of the things in the folder are other folders, which contain files and more folders, and so on, as deep as you like. But there is a short answer:
The number of files in a folder is the number of files directly inside it, plus, for each folder inside it, the number of files in that folder.
The definition uses itself, yet it isn't circular, because each use is about a smaller folder, and eventually you reach folders with no subfolders, where the answer is just a count. That is recursion: solving a problem by solving smaller instances of the same problem.
Recursion is everywhere once you look. A family tree: your ancestors are your parents and the ancestors of your parents. A Russian matryoshka doll: a doll that may contain a smaller doll, which may contain a smaller one. A sentence in any human language can contain a clause that is itself a sentence. And data in computing is full of it: folders, web pages made of nested elements, expressions like (2 + 3) * (4 - 1) made of smaller expressions, the trees and graphs of the lessons ahead.
This lesson shows how a function can call itself, what Python does to make that work, how to be sure a recursive function is correct and finishes, and how the strategy of divide and conquer (split a problem into parts, solve each part recursively, combine the answers) leads to some of the fastest algorithms known. You'll also learn the tool for analysing such algorithms: recurrences and the master theorem.
Trust the smaller problem
Analogy, not a formal construction
You are in a long queue at a stadium in Dakar and want to know your position. You can't see the front. So you ask the person ahead: "What's your position?" They don't know either, so they ask the person ahead of them, and so on, until the question reaches the person at the front, who says "1". The answers then travel back: "2", "3", …, until the person ahead of you says "57", and you know you are 58th. Nobody had to see the whole queue; each person did one tiny step and trusted the answer from the person in front.
The analogy has every ingredient of a recursive function:
- a base case that is answered directly (the person at the front says "1");
- a recursive case that reduces the problem to a smaller one of the same kind (ask the person ahead) and builds the answer from it (add 1);
- progress: each question is about a queue one person shorter, so the questions must reach the front.
The hardest part for most learners is the middle step, which needs a kind of trust. When you write the recursive case, assume the recursive call returns the right answer for the smaller problem, and only ask: "given that, do I compute the right answer for this one?" This is not wishful thinking; it is exactly the induction hypothesis in a proof by induction, and we'll make it rigorous shortly.
Definitions
Definition— recursive function
A function is recursive if it calls itself, directly or through other functions. A recursive function has one or more base cases, inputs it answers without recursion, and one or more recursive cases, which call the function on smaller inputs and combine the results.
Definition— termination measure
A termination measure for a recursive function is a quantity, computed from the arguments, that is a natural number and strictly decreases with every recursive call (for example , or the length of a list). If such a measure exists and every input at which it can no longer decrease is a base case, the recursion always stops.
Definition— call stack
Each call that has started but not yet returned has a stack frame: a record of its local variables and of where to resume when the call it is waiting for returns. The frames form the call stack: a new call pushes a frame on top; a return pops it off. Only the top frame is running.
First recursive functions
The factorial (with ) satisfies for . That identity is a recursive algorithm:
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive case: a smaller nTheorem— factorial is correct
For every integer , factorial(n) terminates and returns .
Proof
By induction on (see proof techniques). Base: factorial(0) returns 1, which is . Step: let and assume factorial(n - 1) terminates and returns . Then factorial(n) reaches the recursive case, which returns . Termination follows because is a natural number that decreases by 1 at each call and the base case covers 0.
∎
The proof is exactly the "trust" from the intuition section: the induction hypothesis is the trust, and the proof checks the one step. Notice what it does not cover: factorial(-1) calls factorial(-2), and so on, never reaching the base case. The measure stops being a natural number, and the theorem's hypothesis was there for a reason. A careful function would reject negative input with a ValueError.
The same pattern works on lists. The sum of a list is 0 if the list is empty, and otherwise the first item plus the sum of the rest:
def total(xs):
if not xs:
return 0
return xs[0] + total(xs[1:])This is correct, but beware a hidden cost: xs[1:] copies the rest of the list, so each call does work and the whole sum costs . Passing a start index instead of slicing avoids the copies. (In practice, of course, use sum or a loop for this; it's an example of the pattern, not the best way to add numbers.)
What Python does: the call stack
When factorial(4) runs, it reaches 4 * factorial(3) and must wait: it can't multiply until it knows factorial(3). Python saves its place (a stack frame holding n = 4 and "resume at the multiplication") and starts the call factorial(3), which in turn waits for factorial(2), and so on. At the deepest point, five frames are on the stack, for . Then factorial(0) returns 1, its frame is popped, factorial(1) resumes and returns , and the answers flow back up: 1, 2, 6, 24.
The program below prints this process. Each call is indented by its depth, so you can see the stack grow and shrink.
def factorial(n, depth=0):
pad = " " * depth
print(f"{pad}factorial({n}) starts")
if n == 0:
result = 1
else:
result = n * factorial(n - 1, depth + 1)
print(f"{pad}factorial({n}) returns {result}")
return result
factorial(4)Two consequences matter in practice.
- Recursion uses memory. The stack holds one frame per unfinished call, so a recursion of depth uses memory even if each frame is small.
factorial(n)uses memory; the loop version uses . - There is a limit. Python refuses to let the stack grow without bound. By default, standard CPython allows about 1000 nested calls (
sys.getrecursionlimit()tells you the current limit; other environments, including browsers, may set a different value). Beyond it, Python raisesRecursionError: maximum recursion depth exceeded. Sofactorial(5000)fails in a default CPython, while a loop computes it instantly.
Recursion follows the shape of the data
Recursion is most natural when the data is recursive. A list whose items may themselves be lists is like the folder at the start of the lesson, and the code mirrors its definition:
def deep_sum(item):
"""Sum all the numbers in item, which is a number or a list of items."""
if not isinstance(item, list): # base case: a plain number
return item
total = 0
for part in item: # recursive case: add up the parts
total += deep_sum(part)
return total
print(deep_sum([1, [2, 3], [[4], [], 5]])) # 15
# A folder is a dictionary with a number of files and a list of subfolders
home = {"files": 3, "folders": [
{"files": 10, "folders": []},
{"files": 1, "folders": [
{"files": 4, "folders": []},
{"files": 0, "folders": [{"files": 7, "folders": []}]},
]},
]}
def count_files(folder):
return folder["files"] + sum(count_files(sub) for sub in folder["folders"])
print(count_files(home)) # 3 + 10 + 1 + 4 + 0 + 7 = 25Writing deep_sum with loops alone is awkward, because you don't know in advance how deeply the lists are nested; the recursive version handles any depth for free. The termination measure is the nesting depth: each call is on a strictly smaller piece of the structure. Trees, which you'll meet in Trees, are processed this way almost always.
Fibonacci, and the cost of repeating yourself
The Fibonacci numbers are defined by , and for : 0, 1, 1, 2, 3, 5, 8, 13, 21, … They are named after Leonardo of Pisa, called Fibonacci, whose Liber Abaci (1202) posed a puzzle about breeding rabbits that leads to them. But they were known centuries earlier in India, where scholars of Sanskrit poetry, including Virahāṅka and later Hemacandra, counted the rhythms that can be made from short syllables (one beat) and long syllables (two beats): the number of rhythms with beats is .
The definition translates directly into code:
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)It is correct, by the same kind of induction as for factorial. It is also catastrophically slow: fib(40) takes many seconds in Python, and fib(100) would not finish in your lifetime. The reason is visible in its recursion tree:
Theorem— naive Fibonacci makes exponentially many calls
Let be the number of calls made by fib(n), including the first. Then .
Proof
, and . For , a call makes itself plus all the calls of its two subcalls: . Assuming the formula for and , this is .
∎
Since grows like , where is the golden ratio, the running time is : exponential. Yet there are only different subproblems, to . The waste is all repetition.
Two standard fixes:
- Memoisation: keep a dictionary of answers already computed, and look there before recomputing. Each is then computed once, so the time is . Python's
functools.cachedecorator adds this to a function in one line. - Iteration from the bottom up: compute in order, keeping only the last two: time and memory.
Both are the starting points of Dynamic programming, one of the most powerful techniques in algorithm design.
from functools import cache
import time
calls = 0
def fib_naive(n):
global calls
calls += 1
if n < 2:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
@cache
def fib_memo(n):
if n < 2:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
def fib_loop(n):
a, b = 0, 1 # F(0), F(1)
for _ in range(n):
a, b = b, a + b
return a
for n in [10, 20, 25]:
calls = 0
start = time.perf_counter()
value = fib_naive(n)
ms = (time.perf_counter() - start) * 1000
print(f"fib({n}) = {value}: {calls} calls, {ms:.1f} ms")
print(fib_memo(90), fib_loop(90)) # instant
print(fib_loop(1000) % 10**10, "(last ten digits of F(1000))")The global variable calls is used here only to count; the global statement lets the function update it.
Recursion or iteration?
Every recursive function can be rewritten with loops, if necessary by keeping your own explicit stack (a list of pending work) in place of Python's call stack; and every loop can be written as a recursion. So the choice is about clarity, efficiency and limits, not about what is possible.
- Use recursion when the problem has a recursive shape: nested data, trees, divide and conquer. The recursive code is usually shorter and closer to the definition, and its correctness proof is a straightforward induction. The depth is usually small, often .
- Use a loop for simple linear repetition, like summing a list or counting down. The loop needs no stack frames, so it is faster in Python and never hits the recursion limit.
Some languages (Scheme, for example, and many functional languages) guarantee tail-call elimination: if the recursive call is the very last thing a function does, the language reuses the current frame, so such recursions use constant memory, like loops. Python deliberately does not do this. Guido van Rossum, Python's creator, explained why in a 2009 post: it would make tracebacks less informative, and he preferred to keep recursion for problems that genuinely need it.
What about the recursion limit? You can raise it with sys.setrecursionlimit, but cautiously: the limit exists to stop runaway recursion from exhausting the memory set aside for the stack, which can crash the interpreter outright instead of raising a tidy exception. If you need recursion thousands of levels deep, that is usually a sign to write a loop.
import sys
print(sys.getrecursionlimit()) # 1000 in a default CPython
def count_down(n):
if n == 0:
return "done"
return count_down(n - 1)
count_down(500) # fine
count_down(100_000) # RecursionError: maximum recursion depth exceededDivide and conquer
Divide and conquer is a recursive strategy with three steps:
- Divide the problem into smaller subproblems, typically of a constant fraction of the size (often half).
- Conquer each subproblem recursively (very small ones directly).
- Combine the subproblems' answers into an answer for the whole.
Example— Fast exponentiation
To compute , the obvious loop does multiplications. But when is even, and when is odd. So one recursive call on , one squaring and perhaps one more multiplication do the job. The exponent halves each time, so there are about levels and at most about multiplications: the code below computes with 16 multiplications instead of 999. Python's built-in pow uses a form of this idea, and it is how cryptographic software computes the huge powers that Applied cryptography relies on.
Example— Multiplying big numbers
Schoolbook multiplication of two -digit numbers takes digit operations. Splitting each number into a high half and a low half, and with a power of the base, gives : four half-size products, which turns out to be no faster. In 1960 Anatoly Karatsuba, then a student in Moscow, noticed that , so three half-size products suffice. That small saving, applied at every level of the recursion, gives , and CPython uses Karatsuba's method when it multiplies very large integers.
The next lesson, Searching and sorting, uses divide and conquer for binary search, merge sort and quicksort.
def power_slow(x, n):
"""Return (x ** n, number of multiplications), multiplying n - 1 times."""
result, mults = x, 0
for _ in range(n - 1):
result = result * x
mults += 1
return result, mults
def power_fast(x, n):
"""Return (x ** n, number of multiplications), by repeated squaring."""
if n == 0:
return 1, 0
half, mults = power_fast(x, n // 2)
result = half * half
mults += 1
if n % 2 == 1:
result = result * x
mults += 1
return result, mults
for n in [10, 100, 1000, 100_000]:
value, m_fast = power_fast(3, n)
assert value == 3 ** n
if n <= 1000:
_, m_slow = power_slow(3, n)
print(f"3^{n}: slow {m_slow} multiplications, fast {m_fast}")
else:
print(f"3^{n}: fast {m_fast} multiplications (the result has {value.bit_length()} bits)")Recurrences and the master theorem
The running time of a recursive algorithm is naturally described by a recurrence: an equation that gives in terms of at smaller sizes. Fast exponentiation does one call on half the input plus constant work: . An algorithm that splits into two halves and does linear work to combine, like merge sort, has . (Strictly, sizes are rounded, , and for small ; these details don't change the answers here.)
Recursion trees
The most illuminating way to solve such a recurrence is to draw its recursion tree and add up the work level by level. For :
The same method works in general. For , level of the tree has subproblems, each of size , so its total work is
and there are about levels. The level costs form a geometric series with ratio . Everything depends on whether that ratio is below, equal to, or above 1, which gives the three cases of the master theorem.
Theorem— The master theorem (polynomial form)
Let , and be constants, and suppose for large (with rounded up or down), and for small . Then
- if , then ;
- if , then ;
- if , then .
The intuition, from the geometric series: if (that is, ), the costs shrink going down the tree and the root's dominates. If , all levels cost the same . If , the costs grow going down and the leaves dominate; there are of them. A full proof sums the series carefully and handles the rounding; the textbook versions also allow more general combining costs in place of .
| Algorithm | Recurrence | , , | Result |
|---|---|---|---|
| binary search, fast power | 1, 2, 0 | ||
| maximum by halves | 2, 2, 0 | ||
| merge sort | 2, 2, 1 | ||
| Karatsuba multiplication | 3, 2, 1 | ||
| four half-size products | 4, 2, 1 | ||
| Strassen's matrix multiplication | 7, 2, 2 |
The master theorem does not apply when the subproblems shrink by subtraction rather than division. Those recurrences can usually be solved by unrolling them: gives , and gives , which is the number of moves in the Tower of Hanoi, a puzzle published by the French mathematician Édouard Lucas in 1883 (one of the exercises asks you to solve it). For much more on solving recurrences, see Recurrences and generating functions in Lumenary Math.
Common mistakes
Misconception
A base case that can be skipped. def f(n): return 1 if n == 0 else f(n - 2) works for even but runs past 0 for odd . Check that the termination measure can only ever arrive at a base case: here n <= 0 would be safe.
Misconception
"Recursion is slow" or "recursion is elegant, so it's better". Neither. Naive Fibonacci is slow because it repeats work, not because it is recursive; merge sort is recursive and fast. A recursion is as efficient as the algorithm it expresses, plus a modest cost per call.
Misconception
"Recursion uses no memory." Every unfinished call holds a stack frame. A recursion of depth uses memory, and in Python it hits the recursion limit at a depth of about a thousand by default.
Misconception
"The master theorem solves every recurrence." It covers with equal-sized parts shrinking by a constant factor. It does not cover , or uneven splits like ; for those, use recursion trees or substitution.
Exercises
1. Recursion and divide and conquer
Warm-upHumanThe naive function
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
is called as fib(10). How many calls of fib happen in total, including the first one? (Use )
2. Recursion and divide and conquer
CoreHumanSolve .
3. Recursion and divide and conquer
CoreHumanKaratsuba's algorithm splits each -digit number in half and makes three recursive multiplications of half size, plus additions and shifts. Its running time is:
4. Recursion and divide and conquer
CoreComputationalWhich of these functions fails to terminate for some whole number ?
5. Recursion and divide and conquer
CoreComputationalWrite a recursive power(x, n) that returns for a whole number , using at most about multiplications, by repeated squaring:
- ;
- if is even, ;
- if is odd, .
Don't use ** or pow. The checker counts your multiplications: computing a power with may use at most 22.
6. Recursion and divide and conquer
CoreComputationalWrite flatten(nested) that takes a list whose items are numbers or (nested) lists, and returns a flat list of all the numbers, in order, however deeply they are nested:
flatten([1, [2, [3, 4]], [], [[5]]]) == [1, 2, 3, 4, 5]
The starter only handles one level of nesting. Use isinstance(item, list) to tell lists from numbers.
7. Recursion and divide and conquer
CoreComputationalIn the Tower of Hanoi, discs of different sizes sit on peg source, largest at the bottom. Move them all to peg target, one disc at a time, never putting a larger disc on a smaller one, using peg spare as well.
Write hanoi(n, source, target, spare) that returns the list of moves, each a tuple (from_peg, to_peg). The recursive idea: move the top discs out of the way to spare, move the largest disc to target, then move the discs from spare onto it.
8. Recursion and divide and conquer
StretchComputationalSanskrit poets counted rhythms made of short syllables (1 beat, written S) and long syllables (2 beats, written L). Write a recursive rhythms(n) that returns a list of all the strings of S and L whose beats add up to exactly n. For example, rhythms(3) contains "SSS", "SL" and "LS" (in any order), and rhythms(0) is [""]: one rhythm, the empty one.
Hint: a rhythm of beats starts either with S followed by a rhythm of beats, or with L followed by a rhythm of beats.
Further reading and resources
- Tail recursion elimination · Guido van Rossum · 2009Python's creator explains why Python does not optimise tail calls.
- sys.setrecursionlimit · Python Software FoundationWhat the recursion limit protects against, and the risk of raising it.
- functools.cache · Python Software FoundationMemoisation in one line.
- MIT 6.006 Introduction to Algorithms (Spring 2020) · MIT OpenCourseWareLectures on recursion, divide and conquer and recurrences.