Python Tutorial
Recursion in Python
A recursive function solves a problem by calling itself on a smaller version of the same problem. Many problems are naturally recursive: factorials, walking nested folders or JSON, tree and graph traversal, divide-and-conquer sorting, generating permutations.
This lesson covers base cases and recursive cases, how the call stack works, Python's recursion limit, memoization with functools.lru_cache, recursion over nested data, and when an iterative solution is better.
Base Case and Recursive Case
Every recursive function needs a base case that returns without recursing, and a recursive case that moves toward it. Missing or unreachable base cases cause infinite recursion, which Python stops with RecursionError.
The Call Stack and the Recursion Limit
Each call gets its own frame on the call stack with its own local variables. Python limits the depth (1000 frames by default, see sys.getrecursionlimit()) and does not optimise tail calls, so very deep recursion should be rewritten as a loop.
Memoization
Naive recursive Fibonacci recomputes the same values exponentially many times. Caching results — memoization — with @functools.lru_cache or @functools.cache turns it into a linear-time algorithm with one line.
Examples
Factorial, sum of digits and power
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case
def digit_sum(n):
return n if n < 10 else n % 10 + digit_sum(n // 10)
def power(base, exp):
if exp == 0:
return 1
half = power(base, exp // 2)
return half * half * (base if exp % 2 else 1)
print(factorial(5), digit_sum(98765), power(2, 30))120 35 1073741824Memoized Fibonacci and the recursion limit
import sys
from functools import lru_cache
calls = 0
def fib_slow(n):
global calls
calls += 1
return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)
@lru_cache(maxsize=None)
def fib_fast(n):
return n if n < 2 else fib_fast(n - 1) + fib_fast(n - 2)
print(fib_slow(20), "calls:", calls)
print(fib_fast(90))
print(fib_fast.cache_info().misses, "distinct values computed")
print("limit:", sys.getrecursionlimit())
def countdown(n):
return countdown(n - 1) # no base case!
try:
countdown(5)
except RecursionError as e:
print("RecursionError:", e)6765 calls: 21891
2880067194370816120
91 distinct values computed
limit: 1000
RecursionError: maximum recursion depth exceededRecursion over nested data and permutations
def flatten(items):
result = []
for item in items:
if isinstance(item, list):
result.extend(flatten(item))
else:
result.append(item)
return result
def count_keys(data):
if isinstance(data, dict):
return len(data) + sum(count_keys(v) for v in data.values())
if isinstance(data, list):
return sum(count_keys(v) for v in data)
return 0
def permutations(s):
if len(s) <= 1:
return [s]
return [ch + p for i, ch in enumerate(s) for p in permutations(s[:i] + s[i + 1:])]
print(flatten([1, [2, [3, [4, 5]]], 6]))
print(count_keys({"a": 1, "b": {"c": 2, "d": [{"e": 3}]}}))
print(permutations("abc"))[1, 2, 3, 4, 5, 6]
5
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']Common Mistakes
- Forgetting the base case or never moving toward it.
- Using naive recursion for overlapping subproblems without memoization.
- Recursing thousands of levels deep in Python instead of using a loop.
- Raising the recursion limit with sys.setrecursionlimit to hide a design problem.
Key Points to Remember
- Recursion needs a base case and a recursive case that shrinks the problem.
- Each call has its own stack frame; Python's default depth limit is 1000.
- @lru_cache / @cache memoize results to avoid repeated work.
- Recursion suits nested data, trees and divide-and-conquer; loops suit deep linear repetition.
Practice the examples
Change an input, predict the result, then compare it with the output. Explain why the result changes.