Recursion

Base cases, recursive cases, the call stack and when to avoid recursion.

A recursive function solves a problem by calling itself on a smaller version of the same problem. It feels odd at first, but many problems (trees, nested folders, divide-and-conquer) are naturally recursive, and the code ends up shorter than a loop.

Two required parts

• Base case: the smallest problem, answered directly. Without it, the function never stops.
• Recursive case: reduce the problem and call yourself, trusting that the call returns the right answer for the smaller input.

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

print(factorial(5))

120

The call stack

Each call waits for the one it started. factorial(3) becomes 3 * factorial(2), which becomes 3 * (2 * factorial(1)); when the base case returns 1, the stack unwinds multiplying as it goes. Each waiting call uses memory, so Python limits depth (about 1000) and raises RecursionError if you exceed it.

def sum_list(a):
    return 0 if not a else a[0] + sum_list(a[1:])

def reverse(s):
    return s if len(s) <= 1 else reverse(s[1:]) + s[0]

def power(x, n):                    # fast exponent, O(log n)
    if n == 0:
        return 1
    half = power(x, n // 2)
    return half * half * (x if n % 2 else 1)

print(sum_list([1, 2, 3]), reverse("abc"), power(2, 10))

6 cba 1024

Recursion on nested data

Recursion shines when data has no fixed depth, like a nested list or a directory tree.

def flatten(x):
    out = []
    for item in x:
        if isinstance(item, list):
            out.extend(flatten(item))
        else:
            out.append(item)
    return out

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

[1, 2, 3, 4, 5]

The Fibonacci trap

Naive fib(n) = fib(n-1) + fib(n-2) recomputes the same values over and over and takes exponential time. Caching results fixes it, which leads straight into dynamic programming.

from functools import lru_cache

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

print(fib(50))

12586269025

Recursion vs iteration

Anything recursive can be written with a loop and an explicit stack. Prefer a loop when depth could be large or the loop is just as clear; prefer recursion when it mirrors the structure of the problem.

def is_palindrome(s):
    if len(s) <= 1:
        return True
    return s[0] == s[-1] and is_palindrome(s[1:-1])

print(is_palindrome("level"), is_palindrome("stack"))