Python Recursion
A recursive function is a function that calls itself to solve a smaller version of the same problem. Recursion is natural for problems with a repeating structure, such as nested folders, trees and many classic interview questions.
- The base case and the recursive case
- Trace how recursive calls unwind
- Avoid the recursion limit
- Speed up recursion with memoization
How recursion works
Every recursive function needs two parts:
- A base case that answers directly and stops the recursion.
- A recursive case that calls the function on a smaller input.
def countdown(n): if n == 0: # base case print("Lift off!") return print(n) countdown(n - 1) # recursive case: a smaller problem countdown(3)3 2 1 Lift off!
Factorial
5! means 5 × 4 × 3 × 2 × 1. Notice that 5! = 5 × 4!, which is a recursive definition.
def factorial(n): if n <= 1: return 1 return n * factorial(n - 1) print(factorial(5))print(factorial(20))120 2432902008176640000
Trace the calls
Indenting each call by its depth shows how the calls go down to the base case and the results come back up:
def factorial(n, depth=0): pad = " " * depth print(f"{pad}factorial({n})") if n <= 1: result = 1 else: result = n * factorial(n - 1, depth + 1) print(f"{pad}-> {result}") return result factorial(4)factorial(4)
factorial(3)
factorial(2)
factorial(1)
-> 1
-> 2
-> 6
-> 24Sum of digits and reversing a string
def digit_sum(n): if n < 10: return n return n % 10 + digit_sum(n // 10) def reverse(text): if len(text) <= 1: return text return reverse(text[1:]) + text[0] print(digit_sum(40721), reverse("python"))14 nohtyp
Recursion on nested data
Recursion shines when data contains smaller copies of itself, such as lists inside lists:
def flatten(items): flat = [] for item in items: if isinstance(item, list): flat.extend(flatten(item)) # recurse into the sub-list else: flat.append(item) return flat print(flatten([1, [2, [3, 4], 5], [[6]]]))[1, 2, 3, 4, 5, 6]
The recursion limit
Each call uses memory on the call stack. Python stops runaway recursion with a RecursionError (the default limit is about 1000 calls). A missing base case causes it immediately:
def forever(n): return forever(n + 1) forever(0)Traceback (most recent call last):
File "main.py", line 4, in <module>
forever(0)
~~~~~~~^^^
File "main.py", line 2, in forever
return forever(n + 1)
File "main.py", line 2, in forever
return forever(n + 1)
File "main.py", line 2, in forever
return forever(n + 1)
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceededimport sysprint(sys.getrecursionlimit())1000
Do not just raise the limit with sys.setrecursionlimit() to make a deep recursion work. Rewrite it as a loop instead.
Fibonacci and memoization
The naive Fibonacci function recalculates the same values again and again, so it becomes very slow:
calls = 0def fib(n): global calls calls += 1 return n if n < 2 else fib(n - 1) + fib(n - 2) print(fib(20), "calls:", calls)6765 calls: 21891
functools.lru_cache remembers results, so each value is computed only once:
from functools import lru_cache @lru_cache(maxsize=None)def fib(n): return n if n < 2 else fib(n - 1) + fib(n - 2) print(fib(80))print(fib.cache_info().misses, "distinct calls")23416728348467685 81 distinct calls
Recursion or a loop?
def factorial_loop(n): result = 1 for i in range(2, n + 1): result *= i return result print(factorial_loop(5), factorial_loop(5) == 120)120 True
| Recursion | Loop | |
|---|---|---|
| Best for | Trees, nested data, divide-and-conquer | Simple repetition |
| Readability | Matches recursive definitions | Matches step-by-step thinking |
| Limits | Recursion depth (about 1000) | None |
| Speed in Python | Slower (function call overhead) | Faster |
Check your understanding
Predict the output
def power(base, exp): if exp == 0: return 1 return base * power(base, exp - 1) print(power(2, 10), power(5, 0))1024 1
Each call multiplies by base once and reduces exp by 1 until the base case returns 1.
Quick quiz
1. What stops a recursive function from calling itself forever?
The base case returns without recursing. The limit is only a safety net that raises an error.
2. What error does Python raise for recursion that is too deep?
Python raises RecursionError: maximum recursion depth exceeded.
3. What does @lru_cache do for a recursive function?
Memoization turns the exponential Fibonacci into a linear one.
Exercise: count files in nested folders
A folder is a dict mapping names to either a file size (int) or another folder (dict). Write a recursive function that returns the total size.
{"a.txt": 10, "img": {"b.png": 200, "old": {"c.png": 50}}, "d.md": 5}265
Hint 1
If a value is a dict, call the function on it; otherwise add the number.
def total_size(folder): size = 0 for value in folder.values(): if isinstance(value, dict): size += total_size(value) else: size += value return size tree = {"a.txt": 10, "img": {"b.png": 200, "old": {"c.png": 50}}, "d.md": 5}print(total_size(tree))265
The base case is implicit: a folder with no sub-folders adds up its numbers without recursing. Each sub-folder is handled by the same function.
Program Practice
39 Python Function Programs
Every program has a step-by-step explanation, colour-coded code and its real output.
Python recursion FAQ
What is recursion in Python?
Recursion is when a function calls itself to solve a smaller instance of the same problem, until it reaches a base case that it can answer directly.
What is the maximum recursion depth in Python?
The default limit is 1000 frames. sys.getrecursionlimit() shows it. Deep problems should use a loop instead.
Is recursion faster than iteration in Python?
No. Python function calls are relatively expensive, so a loop is usually faster. Use recursion when it makes the code clearer.