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=24

Factorial: 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))   # 120

Recursion 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 720

Practical 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 directories

Edge 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 False

Mental 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")