Recursion
Recursion is when a function calls itself to solve a smaller version of the same problem. It's a natural fit for problems that contain smaller copies of themselves, such as folders inside folders or lists inside lists, and it's a classic topic in programming interviews.
The two essential parts
Every recursive function needs:
- A base case: a simple situation where the function returns an answer directly, without calling itself. This is what stops the recursion.
- A recursive case: where the function calls itself with a smaller or simpler input, moving closer to the base case.
def countdown(n):
if n == 0: # base case
print("Liftoff!")
return
print(n)
countdown(n - 1) # recursive case: a smaller problem
countdown(3)
countdown(3) prints 3 and calls countdown(2), which prints 2 and calls countdown(1), which prints 1 and calls countdown(0). That call hits the base case and stops.
Factorial: the classic example
The factorial of n, written n!, is n × (n − 1) × … × 1. So 5! = 5 × 4 × 3 × 2 × 1 = 120. Notice that 5! = 5 × 4!, so factorial is defined in terms of a smaller factorial, which makes it perfect for recursion.
def factorial(n):
if n <= 1: # base case: 1! = 1 (and 0! = 1)
return 1
return n * factorial(n - 1) # recursive case
print(factorial(5))
print(factorial(1))
What happens on the call stack
Each call waits for the one below it to return. Python keeps track of the waiting calls on the call stack. The calls go down until the base case, then the results are multiplied on the way back up:
factorial(5) = 5 * factorial(4) = 5 * (4 * factorial(3)) = 5 * (4 * (3 * factorial(2))) = 5 * (4 * (3 * (2 * factorial(1)))) = 5 * (4 * (3 * (2 * 1))) = 120
factorial(1) answers straight away; its result then travels back up, being multiplied at each level until factorial(5) returns 120.More recursive examples
Adding up a list
The sum of a list is its first item plus the sum of the rest. The sum of an empty list is 0.
def sum_list(numbers):
if not numbers: # empty list
return 0
return numbers[0] + sum_list(numbers[1:])
print(sum_list([4, 7, 1]))
Reversing a string
def reverse(text):
if len(text) <= 1:
return text
return reverse(text[1:]) + text[0]
print(reverse("Kuza"))
Where recursion really shines: nested data
When data can be nested to any depth, loops alone struggle, but recursion handles it naturally. This function adds up every number in a list, no matter how deeply lists are nested inside it.
def deep_sum(items):
total = 0
for item in items:
if isinstance(item, list):
total += deep_sum(item) # a list inside: recurse
else:
total += item
return total
data = [1, [2, 3], [4, [5, 6]]]
print(deep_sum(data))
The same idea is used to walk through folders on a disk, menus with sub-menus and family trees.
Recursion vs. loops
Anything written recursively can also be written with a loop. For factorial, the loop is simple and avoids the overhead of many function calls:
def factorial_loop(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
print(factorial_loop(5))
| Recursion | Loops |
|---|---|
| Elegant for nested or tree-shaped problems | Usually clearer for simple repetition |
| Each call uses memory on the call stack | Uses a fixed, small amount of memory |
| Limited depth in Python (about 1,000 calls by default) | Can repeat millions of times |
Dangers and limits
A missing or unreachable base case. If the function never stops calling itself, Python eventually raises a RecursionError ("maximum recursion depth exceeded"). For example, countdown(-1) with the code above would never reach n == 0. Using if n <= 0: as the base case is safer. Always check that every recursive call moves closer to the base case.
CPython limits recursion depth to protect your computer from runaway calls. You can check the limit:
import sys print(sys.getrecursionlimit())
That's the default; it can be raised with sys.setrecursionlimit(), but needing to is usually a sign that a loop would be better.
Repeated work: the Fibonacci trap
In the Fibonacci sequence, each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, …
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print([fib(n) for n in range(10)])
This works but is very slow for larger n, because the same values are calculated again and again: fib(50) would make about 40 billion calls. The standard library can remember (cache) results for you:
from functools import cache
@cache
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(50))
The @cache line is a decorator; it makes each fib(n) calculate only once, so the answer appears instantly.
Key points
- A recursive function calls itself on a smaller version of the problem.
- It must have a base case that stops the recursion, and each call must move towards it.
- Recursion suits nested, tree-like data; loops are usually better for simple repetition.
- Python's default depth limit is about 1,000 calls; going deeper raises
RecursionError. - Avoid repeated work in recursion with caching, such as
functools.cache.
Tip: use the ← and → keys to move between pages.
