Memoization

Memoization is the single technique that turns exponential algorithms (which would run for centuries) into polynomial ones (which finish in milliseconds). It is the foundation of dynamic programming, which you will study next, and it appears everywhere in AI: caching the results of expensive computations in large language models, making inference on small devices feasible, accelerating retrieval in RAG systems, and avoiding redundant work in agentic loops. Master memoization and you will understand the core of algorithmic performance engineering.

Memoization is the idea of remembering the answers to questions you've already answered, so you don't have to compute them again. Imagine you're a student solving a worksheet of arithmetic problems. Some problems are repeated. If you solve the same problem twice, you waste time. Instead, you keep a small notebook: every time you solve a problem, you write down the problem and its answer. The next time you see it, you just look it up, without doing the arithmetic again. Memoization is exactly that, but for functions in a program. When a function is called with the same arguments a second time, instead of recomputing the result from scratch, the program looks it up in a cache. This only works if the function is 'pure' — that is, the same input always gives the same output, and calling it doesn't change anything else in the world. If a function isn't pure, the cache would return stale or wrong answers. Memoization is a way to trade a little extra memory for a lot less time — a classic space-time tradeoff.

Think of a chef preparing a large meal. The recipe has many steps, and some steps are reused. For example, the chef needs to make a stock that is used in three different dishes. Instead of making the stock three times, the chef makes it once, stores it in a container, and then uses it from the container each time. The stock is the result of a function (make_stock) with no arguments. But imagine the stock recipe depends on the type of stock (chicken, vegetable, beef). If the chef is making both a chicken soup and a chicken sauce, both need chicken stock. The chef can make chicken stock once, label the container 'chicken stock', and reuse it. The label is the cache key; the container is the cache. The chef would not make it again unless it was needed for a different kind. This analogy holds until we consider that the stock might spoil — in a program, the cache doesn't spoil. But it can grow too large, so we might need to evict old entries, just like a chef might discard old stock to make room in the fridge. That's the eviction policy part of memoization.

Memoization is a technique where a function's results are stored in a cache keyed by its arguments, so that repeated calls with the same arguments return the stored result immediately instead of recomputing it.

Memoization is the top-down implementation of dynamic programming, which you will learn next. It is a direct application of the space-time tradeoff you will study: you spend memory on a cache to save computation time. Your notes on Big-O Notation will be useful here, because memoization changes the complexity class of many recursive functions from exponential (2^n) to polynomial (n or n^2). It also connects to binary search in spirit: both use a clever organization of data (sorted array vs. cache) to avoid redundant work.