Memoization avoids repeating the same computation by storing a function result and reusing it when the function is called again with the same inputs.

if input is cached:
    return cached result
result = f(input)
cache[input] = result
return result

The cache can use a map, array or another lookup structure depending on the input domain. What matters is that the same relevant input can retrieve the previously computed result.

When it is safe

The cleanest case is a pure function: equal inputs always produce the same output and the call has no relevant side effects. Replacing a repeated call with its cached result then preserves behavior.

Caching an impure computation requires care because a reused result can become stale or skip effects that were expected to happen again.

Time–space trade-off

Memoization exchanges memory for computation. A cache hit can replace expensive work with a lookup, but cached results consume space. An unbounded cache can grow indefinitely; bounded caches need an eviction policy and may later recompute discarded results.

Memoization is especially useful when expensive subproblems recur, including many recursive algorithms, but it is not limited to recursion.