Recursion

Difficulty: Advanced

Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller sub-problems. Every recursive function must have two essential components: a base case that stops the recursion, and a recursive case that moves the problem closer to the base case.

The base case is the simplest version of the problem that can be solved directly without further recursion. Without a proper base case, a recursive function will keep calling itself indefinitely until Python raises a RecursionError due to exceeding the maximum call stack depth (default 1000 frames). The recursive case is where the function calls itself with a modified argument that progresses toward the base case.

Classic examples of recursion include computing factorials, generating Fibonacci numbers, and traversing tree-like data structures. Factorial of n (n!) is defined as n * (n-1)!, with the base case being 0! = 1. The Fibonacci sequence is defined as fib(n) = fib(n-1) + fib(n-2), with base cases fib(0) = 0 and fib(1) = 1.

While recursion produces elegant and readable code, it can be inefficient for certain problems. Naive recursive Fibonacci has exponential time complexity O(2^n) because it recomputes the same sub-problems repeatedly. Techniques like memoization can drastically improve performance by caching previously computed results. Python provides functools.lru_cache as a built-in memoization decorator.

Understanding how the call stack works is crucial for debugging recursive functions. Each recursive call adds a new frame to the stack, and frames are removed (popped) as each call returns its result. Visualizing this stack helps you trace through recursive logic and identify issues like missing base cases or incorrect recursive steps.

Code examples

Factorial using recursion

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

print(factorial(5))
print(factorial(0))
print(factorial(10))

The base case returns 1 when n is 0. Otherwise, the function multiplies n by factorial(n-1), unwinding the call stack once the base case is reached.

Fibonacci with and without memoization

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

print(fib(10))

from functools import lru_cache

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

print(fib_memo(50))

The naive fib function recomputes sub-problems, making it very slow for large n. The memoized version caches results, reducing time complexity from O(2^n) to O(n).

Sum of a list using recursion

def recursive_sum(lst):
    if len(lst) == 0:
        return 0
    return lst[0] + recursive_sum(lst[1:])

print(recursive_sum([1, 2, 3, 4, 5]))
print(recursive_sum([]))

The base case handles an empty list. Each recursive call processes the first element and recurses on the remaining slice of the list.

Key points

Every recursive function must have at least one base case to prevent infinite recursion.
Python's default recursion limit is 1000 frames. You can change it with sys.setrecursionlimit(), but deep recursion should usually be converted to iteration.
Memoization (functools.lru_cache) turns exponential recursive solutions into polynomial ones by caching results.

Concepts covered

base case, recursive case, call stack