Prerequisite:

Some problems have a shape that makes loops awkward and recursion natural. Understanding recursion won’t just expand your toolkit - it’ll change how you see problems with self-similar structure: trees, nested data, divide-and-conquer algorithms.

What Recursion Is

A recursive function is one that calls itself with a smaller or simpler version of the problem. The key insight: if you can solve a big problem by solving a smaller version of the same problem, recursion is a natural fit.

Every recursive function needs two things:

  • Base case - the simplest input where you return a result directly, without another call.
  • Recursive case - the general case, where you call yourself with a smaller input.

Forgetting the base case means the function calls itself forever (until Python raises a RecursionError).

Stack Frames

Each function call in Python gets its own stack frame - a block of memory holding the function’s local variables and where to return to. When a function calls itself, a new frame is pushed onto the call stack. When it returns, that frame is popped.

Visualise factorial:

def factorial(n):
    if n == 0:       # base case
        return 1
    return n * factorial(n - 1)

factorial(4)
# factorial(4) → 4 * factorial(3)
#                    → 3 * factorial(2)
#                           → 2 * factorial(1)
#                                  → 1 * factorial(0)
#                                         → 1
# Unwinding: 1 → 1 → 2 → 6 → 24

The call stack grows as we go deeper, then shrinks as each call returns its value upward.

Fibonacci and the Exponential Cost Problem

Fibonacci is the other canonical example:

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

This is elegant but slow. fib(5) calls fib(4) and fib(3). fib(4) calls fib(3) again. The same subproblems are solved over and over, giving $O(2^n)$ time - unusable for large inputs.

The fix is memoization (covered below).

Tree Traversal: The Natural Recursive Problem

Recursion really shines with trees. A tree node has a value and children, each of which is itself a tree node - that’s a recursive structure, so recursive code fits perfectly:

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []

def tree_sum(node):
    """Sum all values in a tree."""
    total = node.value
    for child in node.children:
        total += tree_sum(child)   # same problem, smaller input
    return total

root = Node(1, [Node(2, [Node(4), Node(5)]), Node(3)])
print(tree_sum(root))   # 15

Writing this with a loop would require manually managing a stack. Recursion makes it read like the problem description.

When Recursion Is Elegant

Reach for recursion when:

  • The problem is defined recursively (trees, nested structures, divide-and-conquer).
  • The recursive solution is significantly clearer than the iterative one.
  • Input depth is bounded and won’t overflow the stack.

Common examples: directory traversal, parsing nested expressions, merge sort, quicksort, depth-first search.

When to Prefer Iteration

Python’s default recursion limit is around 1000 frames. A list with 2000 elements processed recursively will raise RecursionError. For flat data structures (lists, arrays), a loop is almost always better: it’s faster, uses constant stack space, and won’t hit limits.

You can raise the limit with sys.setrecursionlimit, but that’s a workaround, not a solution. If you’re hitting it, consider converting to iteration or using an explicit stack.

Memoization to Fix Fibonacci

Cache results so each subproblem is solved once:

import functools

@functools.lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(50))   # 12586269025 - instant

lru_cache stores the return value for each set of arguments. The second time fib(3) is called, it returns immediately from the cache. This brings Fibonacci from $O(2^n)$ to $O(n)$.

Tail Recursion

A tail recursive function makes its recursive call as the very last thing it does - no pending work after the call returns. Many languages optimise tail calls to reuse the current stack frame (constant stack space). Python does not. A tail-recursive function in Python still uses $O(n)$ stack frames. The concept is worth knowing, but in Python, convert deep tail recursion to a loop.

Examples

Flattening a nested list recursively:

def flatten(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten(item))   # recurse on sublists
        else:
            result.append(item)
    return result

nested = [1, [2, [3, 4], 5], [6, 7]]
print(flatten(nested))   # [1, 2, 3, 4, 5, 6, 7]

Binary search - recursive vs iterative:

# Recursive
def binary_search_rec(arr, target, lo, hi):
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, hi)
    else:
        return binary_search_rec(arr, target, lo, mid - 1)

# Iterative
def binary_search_iter(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

data = list(range(0, 100, 2))   # [0, 2, 4, ..., 98]
print(binary_search_rec(data, 42, 0, len(data) - 1))   # 21
print(binary_search_iter(data, 42))                     # 21

Both run in $O(\log n)$ time. For binary search specifically, the iterative version is preferred in Python - the input can be large and the loop is simpler. But the recursive version shows the algorithm’s structure clearly, which is why it’s often used to teach the concept.

Read Next: