Recursion is a function solving a problem by calling itself with a smaller version of that same problem, until it reaches a version simple enough to answer directly.
def factorial(n):
if n <= 1:
return 1 # base case — stops the recursion
return n * factorial(n - 1) # recursive case
factorial(5) # 5 * 4 * 3 * 2 * 1 = 120def count_down(n):
# Missing base case — this never stops on its own
print(n)
count_down(n - 1)
# count_down(5) eventually raises:
# RecursionError: maximum recursion depth exceededThe most common recursion bug
Every recursive function needs a base case that's actually reachable — a base case that never triggers fails exactly the same way as no base case at all.
Unlike some languages, Python enforces a default limit (usually 1000) on how deep a recursive call chain can go, specifically to catch runaway recursion before it crashes the interpreter.
import sys
print(sys.getrecursionlimit()) # 1000, by default
# Raising it is possible but rarely the right fix —
# it usually means the problem should be solved with a loop instead
sys.setrecursionlimit(3000)def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
[fibonacci(i) for i in range(8)]
# [0, 1, 1, 2, 3, 5, 8, 13]| Recursion | A loop |
|---|---|
| Often reads more naturally for a naturally recursive problem (traversing a tree, nested data) | Usually faster and uses less memory for a simple repeated task |
| Each call adds a call stack frame — deep recursion can hit Python's recursion limit | No stack depth concern regardless of how many iterations |
A real optimization for recursive functions
The Fibonacci example above recalculates the same values repeatedly — genuinely slow past small inputs. The earlier @functools.lru_cache decorator (from the Decorators lesson) fixes this specific problem by caching each result the first time it's computed.