How would you implement memoization for a recursive function, and what tradeoffs exist between manual caching and `functools.lru_cache`?

Memoization stores the result of a pure function keyed by its arguments so repeated calls skip the work. For a recursive function with overlapping subproblems, like Fibonacci or grid DP, it turns exponential time into linear time (each distinct argument is computed once) at the cost of O(n) memory. The manual version is a decorator holding a dict; the standard-library version is functools.lru_cache (bounded, LRU eviction) or functools.cache (3.9+, unbounded, simpler and slightly faster).

Manual vs lru_cache trade-offs. lru_cache is implemented in C, thread-safe for its own bookkeeping, supports maxsize and typed=True, offers cache_info() and cache_clear(), and handles keyword arguments, so I use it by default. A manual cache is worthwhile when you need custom behavior: TTL expiry, custom keys for unhashable arguments, per-instance caches, metrics, or cache invalidation. Both require hashable arguments and a pure, deterministic function; caching functions with side effects or time-dependent results is a bug.

Pitfalls I check in review: (1) unbounded caches (maxsize=None or functools.cache) grow forever in a long-running service, so bound them or clear them; (2) @lru_cache on an instance method includes self in the key, which keeps every instance alive and leaks memory, so use a per-instance cache, functools.cached_property for no-argument values, or cache a module-level function; (3) returned mutable objects are shared, so a caller who mutates the cached list corrupts later results - return tuples or copies; (4) f(1, 2) and f(a=1, b=2) are cached under different keys; (5) concurrent calls may compute the same value more than once, since the lock protects the cache but not the function call, so it is not a stampede protection.

Recursion limits matter: memoized top-down recursion still uses stack depth equal to the dependency chain, so the default limit (about 1000 frames) fails for deep inputs. Options are bottom-up dynamic programming with a loop (best), an explicit stack, or raising sys.setrecursionlimit cautiously; the last risks a hard crash on deep stacks. For distributed or multi-process services, in-process caches are per-process and cannot be invalidated centrally, so use an external cache such as Redis or a TTL cache library. Version note: functools.cache needs 3.9+, and lru_cache without parentheses (@lru_cache) works from 3.8.