Python Recursion

Recursion is a technique where a function calls itself to solve a problem by breaking it into smaller, identical sub-problems. Each call works on a simpler version of the original problem until it reaches a trivial case — the base case — that can be answered directly.

This chapter covers:

• How recursion works and what the call stack looks like
• Base case and recursive case
• Classic recursive problems: factorial, Fibonacci, power, flatten
• Recursion vs iteration — when to pick each
• Python's recursion limit and how to work around it
• Memoization with functools.lru_cache

How Recursion Works

When a function calls itself, Python pushes a new stack frame onto the call stack for each call. Each frame keeps its own local variables. When the base case is hit, the frames start returning in reverse order — last in, first out — until the original call receives its final answer.

A valid recursive function always has two parts:

Without a base case (or with one that is never reached), the function calls itself forever and Python raises a RecursionError.

A Simple Example: Countdown

The following function counts down from n to zero and then prints "Go!". It is easy to trace because each call reduces n by one until n <= 0.

def countdown(n):
    if n <= 0:         # base case
        print("Go!")
        return
    print(n)
    countdown(n - 1)   # recursive case

countdown(5)

Output:

5
4
3
2
1
Go!

Trace of the call stack:

1. countdown(5) prints 5, calls countdown(4)
2. countdown(4) prints 4, calls countdown(3)
3. … and so on …
4. countdown(0) prints "Go!" and returns — unwinding begins

Factorial

The factorial of n (written n!) is the product of all positive integers up to n. It is defined recursively as:

• 0! = 1 (base case)
• n! = n × (n − 1)! (recursive case)

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

print(factorial(5))    # 120
print(factorial(0))    # 1
print(factorial(10))   # 3628800

factorial(5) expands like this before any value is returned:

factorial(5)
  5 * factorial(4)
        4 * factorial(3)
              3 * factorial(2)
                    2 * factorial(1)
                          1          ← base case

Then the multiplications happen on the way back up: 1 → 2 → 6 → 24 → 120.

Fibonacci Sequence

The Fibonacci sequence is defined by: each number is the sum of the two before it — 0, 1, 1, 2, 3, 5, 8, 13, …

def fibonacci(n):
    if n <= 0:   # base case
        return 0
    if n == 1:   # base case
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(8):
    print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8 13

This is correct but slow for large n — fibonacci(40) makes millions of redundant calls. See Memoization below for the fix.

Sum of a List

Recursion works naturally on lists: process the first item, then recurse on the rest.

def sum_list(lst):
    if not lst:              # base case — empty list
        return 0
    return lst[0] + sum_list(lst[1:])

print(sum_list([1, 2, 3, 4, 5]))   # 15
print(sum_list([]))                 # 0

lst[1:] creates a new list with the first element removed, making the problem one item smaller each time.

Raising a Number to a Power

def power(base, exp):
    if exp == 0:          # base case: anything to the power 0 is 1
        return 1
    return base * power(base, exp - 1)

print(power(2, 10))   # 1024
print(power(3, 4))    # 81
print(power(5, 0))    # 1

Flattening a Nested List

Some problems are inherently recursive — they have the same structure at every level. Flattening an arbitrarily nested list is one of them.

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

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

This is hard to write cleanly with iteration alone because the nesting depth is unknown.

Recursion vs Iteration

Most recursive algorithms can be rewritten as iterative loops, and vice versa.

Iterative factorial

def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_iterative(5))   # 120

Guideline: choose recursion when the problem naturally decomposes into smaller identical sub-problems and the depth is modest. Choose iteration when you need high performance or the depth could be large.

Python's Recursion Limit

Python limits the call stack to 1 000 frames by default to prevent a stack overflow from crashing the process.

import sys
print(sys.getrecursionlimit())   # 1000

If your function exceeds this limit you will see:

RecursionError: maximum recursion depth exceeded

You can raise the limit with sys.setrecursionlimit(n), but do so cautiously — a very deep stack can exhaust system memory. For genuinely deep recursion, rewrite the algorithm iteratively or use Python generators to simulate a stack manually.

Memoization

Naive recursive Fibonacci is exponentially slow because it solves the same sub-problems over and over. Memoization caches the result of each unique call so it is computed only once.

Manual cache with a dictionary

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 0:
        return 0
    if n == 1:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(10))   # 55
print(fibonacci(30))   # 832040

Using functools.lru_cache

The standard library provides a decorator that handles caching automatically:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))   # 55
print(fibonacci(50))   # 12586269025

@lru_cache turns an otherwise exponential algorithm into linear time with zero extra code inside the function body. It is the idiomatic Python approach for memoizing pure recursive functions.

Binary Search (Recursive)

Binary search is a classic divide-and-conquer algorithm: compare the target to the middle element, then recurse on the left or right half.

def binary_search(lst, target, low=0, high=None):
    if high is None:
        high = len(lst) - 1
    if low > high:        # base case: search space exhausted
        return -1
    mid = (low + high) // 2
    if lst[mid] == target:
        return mid
    elif lst[mid] < target:
        return binary_search(lst, target, mid + 1, high)
    else:
        return binary_search(lst, target, low, mid - 1)

nums = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(nums, 7))    # 3
print(binary_search(nums, 1))    # 0
print(binary_search(nums, 15))   # 7
print(binary_search(nums, 4))    # -1  (not found)

Common Gotchas

Missing base case

# This will raise RecursionError
def broken(n):
    return n * broken(n - 1)   # no base case!

Always ask: "What is the simplest input this function must handle without calling itself?"

Infinite recursion from a wrong base case

# factorial of a negative number loops forever
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)   # n goes -1, -2, -3 ...

# Fix: guard at the top
def factorial(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    return n * factorial(n - 1)

Mutable default argument as memo

Using memo={} as a default parameter is convenient but shares state across all top-level calls. For production code, pass the cache explicitly or use @lru_cache.

When to Use Recursion

Recursion is a natural fit for:

• Tree and graph traversal — directory listings, DOM traversal, decision trees
• Divide-and-conquer algorithms — merge sort, quicksort, binary search
• Mathematical definitions — factorial, Fibonacci, combinatorics
• Backtracking — solving mazes, Sudoku, permutation generation
• Nested data structures — JSON/XML parsing, flattening nested lists

For simple sequential loops or large depths, prefer for loops or while loops.

Related Chapters

• Python Functions — the building blocks that recursion is built on
• Python Scope — understanding how local variables work in each frame
• Python While Loops — the iterative alternative
• Python Generators — memory-efficient alternatives for sequences
• Python Iterators — the iteration protocol underlying Python's loop model
• Python Try Except — handling RecursionError gracefully

Practice