memoization

Memoization is an optimization technique that stores the result of a function call against the arguments that produced it, so a later call with the same arguments returns the stored value instead of recomputing it. It’s a function-level form of caching that populates its own cache as the program runs.

A memoized function keeps a lookup table, usually a hash table keyed by the arguments. Every call consults that table first. A miss runs the original computation and records the result before returning it, while a hit returns the stored value and skips the work entirely. Because the arguments form the key, they must be hashable.

Not every function is a safe candidate. Memoization assumes referential transparency, meaning that replacing a call with its return value leaves the program’s behavior unchanged. Three common properties break that assumption:

  • Nondeterminism: A function that reads the clock, a random source, or live input returns a different value each time, and a cached copy would freeze the first result in place.
  • External state: A function whose answer depends on a mutable global, a file, or a database keeps handing back the old value after the underlying source changes.
  • Side effects: A function that writes a log line or increments a counter does that work only on the first call, because later calls never reach the body.

The technique pairs naturally with recursion. A naive recursive Fibonacci function recomputes the same intermediate values an exponential number of times, and memoizing it collapses those repeated branches into a linear number of distinct calls. That top-down reuse of overlapping subproblems is one of the two standard dynamic programming strategies, the other being bottom-up tabulation.

The interactive figure below runs both versions of the same computation at one shared call rate, counting how many times each subproblem gets recomputed.

Interactive diagram — enable JavaScript to view.

The speedup is paid for in memory, so an unbounded cache grows with every distinct argument combination it sees. Capping it with a replacement policy such as least recently used bounds that growth at the cost of occasional recomputation. Python exposes both variants through the functools module: @cache for the unbounded version and @lru_cache(maxsize=128) for the capped one.

Donald Michie introduced the idea as the memo function in a 1968 paper in Nature, and the modern name follows from that shorthand for memorandum, something to be remembered.

Caching in Python Using the LRU Cache Strategy

Tutorial

Caching in Python Using the LRU Cache Strategy

Caching is an essential optimization technique. In this tutorial, you'll learn how to use Python's @lru_cache decorator to cache the results of your functions using the LRU cache strategy. This is a powerful technique you can use to leverage the power of caching in your implementations.

intermediate python

For additional information on related topics, take a look at the following resources:

By Martin Breuss • Updated Aug. 28, 2026
Computer Science Glossary Share Feedback