Memoization stores the result of a function call so the same call does not need to be recomputed.
It is the top-down style of dynamic programming.
Core Idea
The recursive function keeps its natural shape. Before solving a state, it checks whether the answer is already stored. If it is, the function returns the stored value.
Memoization is often the easiest way to turn a slow recursive solution into a dynamic programming solution.
Python Example
from functools import lru_cache
@lru_cache(None)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)lru_cache stores results by function argument.
Common Confusions
Memoization does not remove recursion depth. A deeply recursive memoized function can still hit Python’s recursion limit.
The arguments must fully describe the state. If important information is hidden in mutable global data, the cache may return the wrong answer.
When To Use It
Use memoization when the recursive structure is clear and the same states are reached repeatedly.