Recursion

Contents

Recursion#

Python recursion has a default depth limit of 1000. Adjust with sys.setrecursionlimit if needed, but prefer iteration with an explicit stack for very deep work.

import sys
sys.setrecursionlimit(10000)

Memoization caches the result of a pure function by its arguments. functools.cache and lru_cache apply out-of-the-box.

from functools import cache, lru_cache

@cache                                 # unbounded
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

@lru_cache(maxsize=10_000)             # bounded LRU
def parse(s):
    ...

Memoized functions must be pure (same input, same output, no side effects) and arguments must be hashable. For arrays, convert to a tuple before recursing.

References#

Contents