Python Recursion Explained: 9 Examples, Memoization and the Recursion Limit
Python recursion means a function solving a problem by calling itself on a smaller piece of it. Learn base cases with a traced call stack, nine practical examples, how memoization turned 2.7 million calls into 31, why Python stops at about 1,000 levels, and when a loop is the better choice.
- Python recursion needs a base case that stops it and a recursive case that moves toward the base case.
- Python’s default recursion limit is 1000; going deeper raises
RecursionError. Our 5,000-level count failed. - Naive recursive Fibonacci made 2,692,537 calls for
fib(30);functools.lru_cachecut that to 31 computed values. - Recursion shines for trees, nested data and divide-and-conquer. For simple counting, loops are faster and safer.
Some problems contain smaller copies of themselves: a folder holds folders, a JSON object holds objects, a sorted list splits into two sorted halves. Python recursion lets you write the solution for one level and let the function handle the rest by calling itself. Done well, it produces short, clear code. Done carelessly, it crashes with RecursionError or runs for minutes.
Every example ran on Python 3.13.6, with output copied from the run. If functions are new to you, start with our Python tutorial for beginners.
What is recursion in Python?
A recursive function is a function that calls itself. Each call gets its own local variables on Python’s call stack, and waits for the inner call to return before it finishes. The calls pile up until one of them hits a stopping condition, then the results flow back up the stack one by one.
The two parts: base case and recursive case
- Base case: the simplest input, answered directly without another call. Without it, the function never stops.
- Recursive case: breaks the problem into a smaller version and calls itself on that. Each call must move closer to the base case.
Example 1: factorial
def fact(n):
return 1 if n <= 1 else n * fact(n - 1)
print(fact(5)) # 120
The definition mirrors the maths: 5! = 5 x 4!, and 1! = 1. The base case is n <= 1; the recursive case multiplies n by the factorial of a smaller number.
Example 2: tracing the call stack
def fact_trace(n, depth=0):
print(" " * depth + f"fact({n})")
r = 1 if n <= 1 else n * fact_trace(n - 1, depth + 1)
print(" " * depth + f"-> {r}")
return r
fact_trace(3)
# fact(3)
# fact(2)
# fact(1)
# -> 1
# -> 2
# -> 6
The indentation shows the stack growing as calls go down, and shrinking as results return. fact(3) cannot finish until fact(2) returns, which waits for fact(1). Adding a depth parameter like this is the quickest way to debug any recursive function.
Example 3: the recursion limit
import sys
print(sys.getrecursionlimit()) # 1000
def count(n):
return 0 if n == 0 else 1 + count(n - 1)
count(5000)
# RecursionError: maximum recursion depth exceeded
Every call uses a stack frame, and CPython caps the depth to protect itself from running out of memory or crashing. The default limit is 1000 frames. You can raise it with sys.setrecursionlimit(), but that only moves the cliff; very deep recursion can still crash the interpreter. If an input can be thousands of levels deep, such as a long linked list, use a loop instead. Our exception handling guide explains catching errors like this.
Example 4: naive Fibonacci and exponential calls
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
# fib(30) = 832040, calls = 2,692,537, time = 226 ms
Each call spawns two more, and the same values are recomputed again and again: fib(28) is calculated twice, fib(27) three times, and so on. The number of calls grows exponentially, so fib(40) needs about 331 million calls, roughly 123 times as many, which at this rate means about half a minute. Elegant code, terrible algorithm.
Example 5: memoization with lru_cache
import functools
@functools.lru_cache(maxsize=None)
def fib_m(n):
return n if n < 2 else fib_m(n - 1) + fib_m(n - 2)
fib_m(30) # 832040
fib_m.cache_info() # CacheInfo(hits=28, misses=31, maxsize=None, currsize=31)
# time: about 25 microseconds
Memoization stores each result the first time it is computed. Only 31 distinct values were ever calculated, and the run dropped from 226 ms to about 25 microseconds, roughly 9,000 times faster. Reach for it whenever a recursive function solves the same subproblem more than once; our functools guide covers lru_cache and cache.
Memoization does not fix depth, though. Calling fib_m(3000) on an empty cache still raised RecursionError, because the first call has to descend 3,000 levels. The iterative version has neither problem:
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
fib_iter(30) # 832040
len(str(fib_iter(1000))) # 209 digits, no recursion needed
Example 6: flattening nested lists
def flatten(x):
return [y for i in x for y in (flatten(i) if isinstance(i, list) else [i])]
flatten([1, [2, [3, [4, 5]], 6], [[7]]]) # [1, 2, 3, 4, 5, 6, 7]
You do not know in advance how deep the nesting goes, which is exactly when recursion helps. Each call handles one level and delegates any inner list to another call. The same shape works for nested JSON from an API; see Python JSON.
Example 7: walking a tree
tree = {"name": "root", "children": [
{"name": "src", "children": [
{"name": "app.py", "children": []},
{"name": "utils", "children": [{"name": "io.py", "children": []}]}]},
{"name": "README.md", "children": []}]}
def show(node, depth=0):
print(" " * depth + node["name"])
for c in node["children"]:
show(c, depth + 1)
def size(node):
return 1 + sum(size(c) for c in node["children"])
show(tree)
# root
# src
# app.py
# utils
# io.py
# README.md
print(size(tree)) # 6
Trees are recursion’s natural home: a tree is a node plus smaller trees. The base case is implicit, since a node with no children simply loops zero times. Real-world versions include menus, comment threads, organisation charts and the HTML DOM. A directory walk with os.scandir followed the same pattern in our run and returned ['a', 'a/b', 'a/b/f.txt', 'top.txt']; in production, os.walk or pathlib‘s rglob already do this for you.
Example 8: binary search
def bsearch(a, x, lo=0, hi=None):
hi = len(a) - 1 if hi is None else hi
if lo > hi:
return -1
mid = (lo + hi) // 2
if a[mid] == x:
return mid
return bsearch(a, x, mid + 1, hi) if a[mid] < x else bsearch(a, x, lo, mid - 1)
a = list(range(0, 2_000_000, 2)) # one million even numbers
bsearch(a, 1_234_568) # 617284
bsearch(a, 7) # -1
Divide-and-conquer algorithms halve the problem each call, so the depth stays tiny: about 20 levels for a million items, far below the limit. Merge sort and quicksort work the same way. For real code, the standard library’s bisect module is faster and tested.
Example 9: permutations
def perms(s):
if len(s) <= 1:
return [s]
return [c + p for i, c in enumerate(s) for p in perms(s[:i] + s[i+1:])]
perms("abc") # ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
Pick each character as the first, then recursively permute the rest. This backtracking pattern also solves subsets, combinations, Sudoku and maze search. For production use, itertools.permutations is faster and lazy; see our itertools guide.
Tip: before writing a recursive function, say the base case and the “smaller problem” out loud. If you cannot name both, the design is not ready.
Python has no tail call optimisation
def sum_tail(n, acc=0):
return acc if n == 0 else sum_tail(n - 1, acc + n)
sum_tail(5000) # RecursionError
Some languages reuse the stack frame when the recursive call is the very last action (a tail call), so tail-recursive functions never run out of stack. CPython deliberately does not, to keep tracebacks complete. Writing your function in tail-recursive style therefore buys nothing in Python; convert it to a loop instead.
Recursion vs loops: speed and safety
| Task | Recursive | Alternative |
|---|---|---|
fact(500) vs math.factorial(500) |
88.5 microseconds | 8.8 microseconds |
| Count to 100,000 | RecursionError | Loop: works |
fib(30) |
226 ms naive, 25 microseconds memoized | Loop: instant, no depth limit |
Function calls in Python have real overhead, so a recursive version is usually slower than a loop or a built-in. Choose recursion when the data is recursive (trees, nested structures) or when the recursive version is much clearer, and the depth is known to be small. Choose a loop when the depth could be large or performance matters. You can also convert any recursion to a loop with an explicit stack list. Generators with yield from are another elegant way to walk trees lazily.
Common recursion mistakes
- Missing or unreachable base case, leading to
RecursionError. - Not shrinking the problem, for example calling
f(n)instead off(n - 1). - Repeated subproblems without memoization, causing exponential time.
- Mutable default arguments such as
def walk(node, seen=[]), which share state between calls. - Forgetting to return the recursive call’s result, so the function returns
None. - Raising the recursion limit to hide a design problem.
Final thoughts
Python recursion is a way of thinking: solve the smallest case directly, and express every other case in terms of a smaller one. It makes tree walking, nested data, divide-and-conquer and backtracking remarkably clean. Respect the 1,000-frame limit, memoize repeated subproblems, and switch to a loop when depth can grow. Used that way, recursion is one of the most expressive tools in your Python kit.
Frequently asked questions
What is recursion in Python?
Recursion is when a function calls itself to solve a smaller version of the same problem. It needs a base case that returns directly and a recursive case that moves toward that base case.
What is the maximum recursion depth in Python?
The default limit is 1000 frames, which you can read with sys.getrecursionlimit. Exceeding it raises RecursionError. You can raise it with sys.setrecursionlimit, but deep recursion should usually become a loop.
How do I fix RecursionError in Python?
Check that the base case is reachable and that each call shrinks the problem. If the input is genuinely deep, rewrite the function as a loop or use an explicit stack instead of raising the limit.
Is recursion slower than a loop in Python?
Usually yes, because each function call has overhead. In our test a recursive factorial of 500 took about ten times longer than math.factorial. Choose recursion for clarity on recursive data, not for speed.
What is memoization in recursion?
Memoization caches the result of each call so repeated inputs are not recomputed. In Python, the functools.lru_cache decorator adds it in one line and turned millions of Fibonacci calls into 31 computed values in our test.
Keep learning
Need help with testing, WordPress or SEO?
We help teams ship better software and grow their sites. Tell us what you are working on and we will suggest a clear next step.