Recursion
A recursive function solves a problem by calling itself on a smaller version of that same problem, always anchored by a base case that stops the chain.
Recursion is a technique where a function calls itself to solve smaller instances of the same problem, until reaching a case simple enough to answer directly. Every correct recursive function needs two parts: a *base case* that terminates the recursion without a further call, and a *recursive case* that makes progress toward that base case. Python implements recursion using a call stack with a finite default depth, which shapes both how recursion behaves and when it's the wrong tool for the job.
Base Case and Recursive Case
The base case is the condition under which the function returns a value directly, with no further recursive call — it's what stops the recursion. The recursive case is where the function calls itself with an argument that is measurably closer to the base case.
Every recursive call must make measurable progress toward the base case; a recursive case that doesn't shrink the problem never terminates.
def countdown(n):
if n <= 0: # base case
print("Liftoff!")
return
print(n)
countdown(n - 1) # recursive case: n moves closer to the base case
countdown(3)
# 3
# 2
# 1
# Liftoff!The Call Stack
Each recursive call creates a new stack frame holding that call's local variables and its return address. Frames pile up as calls go deeper and unwind (pop off) in reverse order as calls return — last in, first out.
def factorial(n):
if n <= 1:
return 1
print(f"entering factorial({n})")
result = n * factorial(n - 1)
print(f"leaving factorial({n}), result={result}")
return result
factorial(4)
# entering factorial(4) ... entering factorial(2)
# leaving factorial(2), result=2
# leaving factorial(3), result=6
# leaving factorial(4), result=24Factorial: The Canonical Example
Factorial (n! = n * (n-1) * ... * 1, with 0! = 1) is the textbook first recursion example because its mathematical definition is already recursive.
def factorial(n):
if n < 0:
raise ValueError("factorial is undefined for negative numbers")
if n <= 1: # base case: 0! and 1! are both 1
return 1
return n * factorial(n - 1) # recursive case
print(factorial(5)) # 120Recursion Depth and RecursionError
CPython (and Python implementations generally) impose a limit on how deep the call stack can go — by default around 1000 frames — to prevent runaway recursion from crashing the process by exhausting memory. Exceeding it raises RecursionError.
CPython implementation detail: the exact recursion limit and how it's enforced (a frame counter, adjustable via sys.setrecursionlimit()) is a CPython-specific safety mechanism, not a guarantee of the Python language itself.
import sys
print(sys.getrecursionlimit()) # commonly 1000
def infinite(n):
return infinite(n + 1) # no base case reached -> keeps recursing
try:
infinite(0)
except RecursionError as e:
print("Caught:", e)Tree-Like Recursive Problems
Recursion shines on problems with a naturally branching, tree-shaped structure — where each call spawns multiple further calls — such as traversing nested data, computing Fibonacci numbers, or walking a directory tree.
def fibonacci(n):
if n <= 1: # base cases: fib(0)=0, fib(1)=1
return n
return fibonacci(n - 1) + fibonacci(n - 2) # two recursive branches
print([fibonacci(i) for i in range(8)]) # [0, 1, 1, 2, 3, 5, 8, 13]
def flatten(nested):
result = []
for item in nested:
if isinstance(item, list):
result.extend(flatten(item)) # recurse into sub-lists
else:
result.append(item)
return result
print(flatten([1, [2, 3, [4, [5, 6]], 7]])) # [1, 2, 3, 4, 5, 6, 7]Recursion Versus Iteration
Anything recursion can compute, a loop can compute too (and vice versa) — they're equally expressive. Recursion tends to read more naturally for problems that are inherently self-similar (trees, divide-and-conquer algorithms), while iteration is usually more memory-efficient in Python, since it doesn't grow the call stack.
CPython implementation detail: CPython does not perform tail-call optimization (unlike some functional languages), so a deeply recursive Python function always consumes stack frames proportional to its recursion depth — even 'tail-recursive'-looking code gets no special treatment.
# Recursive factorial
def factorial_recursive(n):
return 1 if n <= 1 else n * factorial_recursive(n - 1)
# Iterative factorial — same result, constant stack usage
def factorial_iterative(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
print(factorial_recursive(6), factorial_iterative(6)) # 720 720Practical Usage
Recursion is idiomatic for tree/graph traversal (file systems, JSON/nested data, binary trees), divide-and-conquer algorithms (merge sort, quicksort, binary search), and backtracking (permutations, maze solving). For simple linear repetition, a loop is usually clearer and avoids stack-depth concerns entirely.
from pathlib import Path
def total_size(path: Path) -> int:
if path.is_file():
return path.stat().st_size
return sum(total_size(child) for child in path.iterdir())
# total_size(Path('.')) # recursively sums file sizes through nested directoriesEdge Cases
A missing or unreachable base case causes infinite recursion, ending in RecursionError rather than looping forever silently (unlike a while True with no break, which just hangs). Mutual recursion — two functions calling each other — works the same way but is easy to lose track of when debugging.
def is_even(n):
if n == 0:
return True
return is_odd(n - 1)
def is_odd(n):
if n == 0:
return False
return is_even(n - 1)
print(is_even(10), is_odd(10)) # True FalseMental Model
Think of recursion as delegating: 'I don't know how to solve the whole problem, but I know how to solve the base case, and I know how to reduce any other case to a smaller version of the same problem plus a little extra work.' Trust that the recursive call correctly solves the smaller problem, and focus only on combining its result correctly.
Quick Reference
def recursive_fn(problem):
if is_base_case(problem):
return direct_answer
smaller = shrink(problem)
return combine(recursive_fn(smaller), ...)
sys.getrecursionlimit() # inspect the default depth limit (CPython)
sys.setrecursionlimit(n) # raise/lower it (use with caution — real stack limits still apply)Key Takeaways
Every correct recursive function needs a base case (stops recursion) and a recursive case that makes measurable progress toward it.
Each recursive call adds a new frame to the call stack; exceeding the recursion limit raises RecursionError.
Recursion and iteration are equally powerful; choose recursion for naturally self-similar/tree-shaped problems, iteration when a simple loop is clearer and more memory-efficient.
CPython implementation detail: CPython performs no tail-call optimization — deep recursion always costs stack depth proportional to the number of calls.
A missing or unreachable base case leads to infinite recursion and a RecursionError, not a silent infinite loop.
def countdown(n): print(n) countdown(n - 1) # no base case — never stops def countdown(n): if n <= 0: print("Liftoff!") return print(n) countdown(n - 1)
Without a base case, the recursion never terminates and eventually raises RecursionError once the call stack limit is reached.
def factorial(n): if n <= 1: return 1 return n * factorial(n) # never decreases n — infinite recursion def factorial(n): if n <= 1: return 1 return n * factorial(n - 1)
The recursive call must move toward the base case; calling factorial(n) instead of factorial(n - 1) never shrinks the problem, so it recurses forever.
def fibonacci(n): if n <= 1: return n return fibonacci(n - 1) + fibonacci(n - 2) fibonacci(40) # extremely slow — exponential re-computation from functools import lru_cache @lru_cache(maxsize=None) def fibonacci(n): if n <= 1: return n return fibonacci(n - 1) + fibonacci(n - 2)
Naive recursive Fibonacci recomputes the same subproblems exponentially many times; memoizing with functools.lru_cache (a standard-library tool) turns it into fast linear-time recursion.
What are the two essential parts of any correct recursive function?
A base case that returns a result directly without further recursion, and a recursive case that calls the function again with an argument that makes measurable progress toward the base case.
What happens in CPython if a recursive function never reaches its base case?
The call stack keeps growing with each recursive call until it exceeds the interpreter's recursion limit (commonly around 1000 frames by default), at which point Python raises a RecursionError.
Why is CPython's lack of tail-call optimization relevant to writing recursive Python code?
It means even recursion written in a 'tail-recursive' style still consumes one stack frame per call in CPython, so very deep recursion can hit the recursion limit or use significant memory — unlike languages that optimize tail calls into a loop.
When would you prefer recursion over a loop, and vice versa?
Prefer recursion for naturally self-similar, tree-shaped, or divide-and-conquer problems (tree traversal, nested data flattening, quicksort) where it reads more clearly; prefer iteration for simple linear repetition, where a loop is typically more memory-efficient and avoids recursion-depth concerns.
Why is naive recursive Fibonacci so slow for larger n, and how can you fix it?
Because it recomputes the same subproblems exponentially many times (fibonacci(n-2) is recomputed by both fibonacci(n-1) and fibonacci(n) branches); memoization, e.g. with functools.lru_cache, caches previously computed results and reduces it to linear time.
What is mutual recursion? Give a simple example.
Mutual recursion is when two or more functions call each other rather than themselves directly — e.g. is_even(n) calling is_odd(n-1), and is_odd(n) calling is_even(n-1), each eventually reaching a base case of n == 0.
Can you always convert a recursive algorithm into an equivalent iterative one?
Yes — recursion and iteration are computationally equivalent in expressive power; any recursive algorithm can be rewritten iteratively (often using an explicit stack or queue to replace the implicit call stack), though the recursive version may be more readable for certain problems.
Write a recursive function sum_digits(n) that returns the sum of the digits of a non-negative integer n.
def sum_digits(n): if n < 10: return n return n % 10 + sum_digits(n // 10) print(sum_digits(12345))
15 — 1+2+3+4+5 = 15, computed by peeling off the last digit (n % 10) and recursing on the rest (n // 10) until a single digit remains.
What does this print?
10 — it computes 4 + 3 + 2 + 1 + 0 = 10, a recursive sum from n down to 0.
Write a recursive function count_nested(lst) that counts how many integers appear anywhere in a possibly nested list of lists.
def count_nested(lst): count = 0 for item in lst: if isinstance(item, list): count += count_nested(item) else: count += 1 return count print(count_nested([1, [2, 3, [4, 5]], 6]))
6 — it recursively descends into every nested list and counts each non-list item (1, 2, 3, 4, 5, 6).
What does this print, and why?
'caught' — f(n) has no base case and calls itself endlessly, so it exceeds the artificially lowered recursion limit of 50 and raises RecursionError, which is caught and handled.
def mystery(n):
if n == 0:
return 0
return n + mystery(n - 1)
print(mystery(4))import sys
sys.setrecursionlimit(50)
def f(n):
return f(n + 1)
try:
f(0)
except RecursionError:
print("caught")