How to write recursive functions¶
This guide covers practical patterns for writing recursive functions in Python. Recursion is a technique where a function calls itself to solve a problem by breaking it into smaller instances of the same problem.
The structure of a recursive function¶
Every recursive function needs two parts:
- A base case that stops the recursion and returns a value directly
- A recursive case that calls the function with a smaller or simpler input
If you forget the base case, the function will call itself indefinitely until Python raises a RecursionError.
def countdown(n: int) -> None:
"""Print a countdown from n to 1."""
if n <= 0: # Base case
print("Go!")
return
print(n)
countdown(n - 1) # Recursive case
countdown(5)
Converting an iterative approach to recursion¶
Any loop can be rewritten as recursion. Here is the factorial function in both styles.
# Iterative version
def factorial_iterative(n: int) -> int:
result = 1
for i in range(2, n + 1):
result *= i
return result
# Recursive version
def factorial(n: int) -> int:
if n <= 1: # Base case
return 1
return n * factorial(n - 1) # Recursive case
print(f"Iterative: {factorial_iterative(6)}")
print(f"Recursive: {factorial(6)}")
The recursive version mirrors the mathematical definition directly: n! = n * (n - 1)! with 0! = 1.
Flattening nested lists¶
Recursion is well suited to processing nested data structures where the depth is not known in advance.
def flatten(data: list) -> list:
"""Flatten a nested list structure into a single list."""
result = []
for item in data:
if isinstance(item, list):
result.extend(flatten(item)) # Recurse into nested lists
else:
result.append(item)
return result
nested = [1, [2, 3], [4, [5, 6, [7]]], 8]
print(flatten(nested))
Traversing tree structures¶
Trees are a natural fit for recursion. The following example traverses a file-system-like tree represented as nested dictionaries.
file_tree = {
"src": {
"main.py": 120,
"utils": {
"helpers.py": 45,
"validators.py": 80,
},
},
"tests": {
"test_main.py": 95,
},
"README.md": 30,
}
def list_files(tree: dict, prefix: str = "") -> list[str]:
"""List all file paths in a nested directory tree."""
paths = []
for name, value in tree.items():
full_path = f"{prefix}/{name}" if prefix else name
if isinstance(value, dict):
paths.extend(list_files(value, full_path)) # Recurse into subdirectory
else:
paths.append(full_path)
return paths
for path in list_files(file_tree):
print(path)
Summing values in a nested structure¶
You can combine traversal with accumulation. This function sums all the file sizes in the tree above.
def total_size(tree: dict) -> int:
"""Calculate the total size of all files in a directory tree."""
total = 0
for value in tree.values():
if isinstance(value, dict):
total += total_size(value)
else:
total += value
return total
print(f"Total size: {total_size(file_tree)} lines")
def broken_countdown(n: int) -> None:
"""This function is missing a base case."""
print(n)
broken_countdown(n - 1) # Never stops
try:
broken_countdown(5)
except RecursionError:
print("RecursionError: maximum recursion depth exceeded")
Input not getting smaller¶
The recursive case must move towards the base case. If the input does not change or grows, the function will not terminate.
def broken_sum(n: int) -> int:
"""This function does not reduce the problem — n + 1 moves away from the base case."""
if n <= 0:
return 0
return n + broken_sum(n + 1) # Wrong direction
try:
broken_sum(3)
except RecursionError:
print("RecursionError: the input grows instead of shrinking")
The recursion limit¶
Python sets a recursion limit to prevent stack overflows. You can inspect and change it using the sys module, but increasing it is rarely the right solution.
import sys
print(f"Current recursion limit: {sys.getrecursionlimit()}")
# You can increase it if absolutely necessary
# sys.setrecursionlimit(5000)
# However, if your recursion goes that deep, consider converting to an
# iterative approach instead.
Use sys.setrecursionlimit() only when you are certain the recursion depth is bounded and you understand the memory implications. For most problems, exceeding the default limit signals that an iterative approach would be more appropriate.
Tail recursion and Python¶
In some languages, a function that returns the result of its recursive call directly (without further computation) can be optimised by the compiler to reuse the same stack frame. This is called tail-call optimisation.
Python does not perform tail-call optimisation. The following function is tail-recursive in structure, but Python still allocates a new stack frame for every call.
def factorial_tail(n: int, accumulator: int = 1) -> int:
"""Tail-recursive factorial — but Python does not optimise this."""
if n <= 1:
return accumulator
return factorial_tail(n - 1, n * accumulator)
print(factorial_tail(6))
Because Python does not optimise tail recursion, this version offers no performance advantage over the standard recursive version. If you need to handle large inputs, convert to a loop.
def factorial_loop(n: int) -> int:
"""Iterative factorial — handles arbitrarily large values of n."""
result = 1
while n > 1:
result *= n
n -= 1
return result
print(factorial_loop(6))
print(factorial_loop(100))
Summary¶
The key points for writing recursive functions are as follows:
- Every recursive function needs a base case that stops the recursion and a recursive case that moves towards it
- Recursion works well for nested and tree-shaped data structures
- Always ensure the input gets smaller (or simpler) with each recursive call
- Python does not optimise tail recursion, so convert to iteration for deep recursions
- If you hit the recursion limit, prefer rewriting iteratively over increasing
sys.setrecursionlimit()