Memoization

What it is

Memoization means storing the result of a computation so you do not have to compute the same thing again later.

If the input repeats, the answer is already available.

When to use it

It shows up a lot when:

• the function is pure
• the computation is expensive
• the same inputs return many times

Recursive problems with repeated subproblems are the classic case.

Common mistake

The classic mistake is calling any cache “memoization.”

The term makes more sense when you store a result based on the input of a function or subproblem.

Better question

Before using it, ask:

1. does the same input really repeat?
2. is the cost of storing worth the cost of recomputing?
3. does the answer depend only on the input, or also on outside state?