Definition
Can a function call itself without running forever?
Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. Every recursive function needs a base case, a simple case it answers directly without calling itself, so that the calls eventually stop. Each waiting call is kept on the call stack.
In simple words
5 factorial is 5 × 4 × 3 × 2 × 1. Notice that it is 5 × (4 factorial). So factorial(5) asks factorial(4), which asks factorial(3), down to factorial(1), the base case, which simply says 1. Then the answers multiply back up: 1, 2, 6, 24, 120.
Overview
- Recursion is when a function solves a problem by calling itself on a smaller version of the same problem.
- Every recursive function needs a base case that stops the calls and a recursive case that moves towards it.
- Each call waits on the call stack until the smaller call returns.
- Python limits recursion depth to about 1,000 calls by default and raises RecursionError beyond it.
- Any recursion can be rewritten as a loop, but trees and divide-and-conquer are clearer recursively.
- Memoisation stores results of earlier calls to avoid repeating work.
Why it matters
Many problems are naturally recursive: folders inside folders, trees in decision trees, game moves in minimax, and the splitting in fast sorts. Recursion lets you write them in a few clear lines.
Key terms
- Recursion
- A function solving a problem by calling itself on a smaller version of it.
- Base case
- The simplest case, answered directly, that stops the recursion.
- Recursive case
- The step that calls the function again on a smaller input.
- Call stack
- The stack of waiting function calls that Python keeps while recursion unfolds.
- RecursionError
- The error raised when the call stack grows too deep, usually because a base case is missing.
- Memoisation
- Storing results of earlier calls so they are not computed again.
Types
Recursive functions are classified by how many times and how they call themselves. These are the main types.
1. Linear (direct) recursion
A function that calls itself once in each call.
- How it works: Each call reduces the problem by a step until the base case, then the results are combined on the way back.
- Example: factorial(n) = n × factorial(n − 1), with factorial(0) = 1; factorial(5) = 120.
- When to use it: Use it for problems defined step by step, such as factorials, sums of lists and counting down.
2. Tree (multiple) recursion
A function that calls itself two or more times in each call, forming a tree of calls.
- How it works: The number of calls can grow exponentially, because the same sub-problems are often solved again and again.
- Example: fib(n) = fib(n − 1) + fib(n − 2); plain fib(30) makes over 1.6 million calls.
- When to use it: Use it for branching problems such as tree traversal and exploring choices; add memoisation (functools.lru_cache) when sub-problems repeat.
3. Tail recursion
Recursion where the recursive call is the very last action of the function.
- How it works: Nothing is left to do after the call returns, so some languages reuse the same stack frame; Python does not, so deep tail recursion can still overflow.
- Example: def count_down(n): if n == 0: return; print(n); count_down(n - 1).
- When to use it: Recognise it, and in Python convert deep tail recursion into a simple loop.
4. Indirect (mutual) recursion
Two or more functions that call each other in a cycle.
- How it works: Function A calls B, and B calls A, each moving towards a shared base case.
- Example: is_even(n) returns is_odd(n − 1), and is_odd(n) returns is_even(n − 1), with n = 0 as the base case.
- When to use it: Use it for grammars and parsers, where rules refer to each other, such as expressions containing terms that contain expressions.
5. Divide-and-conquer recursion
Recursion that splits the input into parts of similar size, solves each and combines them.
- How it works: Splitting in half each time gives about log₂ n levels of calls, which is why such algorithms are fast.
- Example: Merge sort, quick sort and recursive binary search.
- When to use it: Use it for sorting, searching and processing hierarchical data such as folders and decision trees.
Explained in detail
Thinking recursively
Some problems are naturally defined in terms of smaller versions of themselves. The factorial of 5, 5!, is 5 × 4!, and 4! is 4 × 3!, down to 1!, which is simply 1. A folder contains files and other folders, each of which contains files and folders. A recursive function mirrors this: it answers the simplest case directly, the base case, and for anything bigger it does a little work and calls itself on a smaller piece, trusting that call to return the right answer. The trick is to believe the smaller call works, rather than trying to follow every level in your head.
What happens on the call stack
| Call | Waiting for | Returns |
|---|---|---|
| factorial(4) | 4 × factorial(3) | 24 |
| factorial(3) | 3 × factorial(2) | 6 |
| factorial(2) | 2 × factorial(1) | 2 |
| factorial(1) | Nothing: base case | 1 |
Each call waits on the call stack until the call below it returns. When the base case is reached, the answers flow back up: 1, then 2, then 6, then 24. If there is no base case, or the input never gets smaller, the stack keeps growing until Python stops it with RecursionError: maximum recursion depth exceeded. Python's default limit is about 1,000 levels, deliberately low, because deep recursion uses a lot of memory.
When recursion shines
- Tree-shaped data: folders, family trees, web pages made of nested elements, JSON with nested dictionaries.
- Divide-and-conquer algorithms: merge sort and quicksort split the problem and recurse on each half.
- Searching games and puzzles: exploring every possible move, as in the minimax algorithm you will meet in classical AI.
- Decision trees, which are built by splitting data and then building a smaller tree on each part.
The cost of repeating work
A naive recursive Fibonacci function, fib(n) = fib(n - 1) + fib(n - 2), recomputes the same values again and again: fib(30) makes over a million calls. Memoisation fixes this by remembering answers. Adding the decorator @functools.cache above the function makes Python store each result, and fib(30) then needs only 31 distinct calculations. This idea, solving each sub-problem once and reusing the answer, is called dynamic programming and is behind many efficient algorithms. For simple counting and summing, a loop is usually clearer and faster than recursion.
How it works
factorial(4) = 4 × factorial(3) = 4 × 3 × factorial(2) = 4 × 3 × 2 × factorial(1) = 4 × 3 × 2 × 1 ← base case = 24
In code
Factorial, a countdown, and a sum of a list, each with its base case. The indentation shows how deep the calls go.
def factorial(n, depth=0):
print(" " * depth + f"factorial({n})")
if n == 1: # base case
return 1
return n * factorial(n - 1, depth + 1)
print("Result:", factorial(4))
def countdown(n):
if n == 0:
print("Lift off!")
return
print(n)
countdown(n - 1)
countdown(3)
def total(numbers):
if not numbers: # base case: an empty list sums to 0
return 0
return numbers[0] + total(numbers[1:])
print("Sum of [4, 8, 15]:", total([4, 8, 15]))Output
factorial(4)
factorial(3)
factorial(2)
factorial(1)
Result: 24
3
2
1
Lift off!
Sum of [4, 8, 15]: 27Try it yourself
Order the calls on the call stack
For factorial(3), put the events in the order they happen.
- 1factorial(1) reaches the base case and returns 1
- 2factorial(3) is called and waits for factorial(2)
- 3factorial(3) returns 3 × 2 = 6
- 4factorial(2) is called and waits for factorial(1)
- 5factorial(2) returns 2 × 1 = 2
Common mistakes
- Forgetting the base case.
- Not making the problem smaller in each call, so the base case is never reached.
- Using recursion for simple counting that a loop does more clearly.
Check yourself
Summary
- A recursive function calls itself on a smaller problem.
- A base case stops the calls; results then return back up.
- It suits trees, folders and game searches.
Finished reading?
Sources: W3Schools: Python Recursion