memoisation
Caching a function's results by its arguments so that repeated calls return the stored answer instead of recomputing it.
In more detail
Memoisation is top-down dynamic programming: keep the natural recursive code and add a cache. In Python, decorating the function with functools.lru_cache does it in one line. It still uses the call stack, so very deep recursion can hit the recursion limit.
Related terms
- functools.lru_cache — A Python decorator from the functools module that memoises a function, remembering results for arguments it has seen.
- dynamic programming — A technique that solves a problem by breaking it into overlapping subproblems, solving each only once and storing the answers for reuse.
- tabulation — Bottom-up dynamic programming: filling a table of subproblem answers in order from the base cases up, so each entry's inputs are ready before it.
- overlapping subproblems — The property that a recursive solution solves the same subproblems again and again.
Taught in
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers