What Is Memoization in Programming? A Simple Guide

If you have asked yourself "what is memoization in programming?", the short answer is this: memoization is a way to make a function faster by remembering the answers it has already worked out. The first time you call the function with some input, it does the work and saves the result. The next time you call it with the same input, it hands back the saved result instead of doing the work again.

What is memoization in programming?

Memoization is a technique where a function stores its results, keyed by its inputs. Wikipedia describes it as a type of caching, normally built on a hash table, and as a trade of memory for speed. The word comes from "memo," as in a note to yourself. The function writes a note for each answer and checks its notes before it computes anything.

It only works safely on one kind of function: a pure function. A pure function always returns the same output for the same input and changes nothing outside itself. If a function reads the clock, a random number or a file that can change, a saved answer can be wrong the next time.

Think of a maths student who has worked out 17 times 23 once. The second time the question comes up, they read the answer off the page. They do not multiply again.

How memoization works step by step

Every memoized function follows the same four steps.

1. Build a store. Create an empty dictionary, map or object. Call it cache. Its keys are inputs and its values are results.
2. Check the store first. When the function is called, look up the input in cache. If the key is there, return the saved value and stop.
3. Compute on a miss. If the key is missing, do the real work.
4. Save, then return. Put the result in cache under that input, then return it.

A lookup in a dictionary takes close to constant time. So you trade a little memory and a little lookup time for skipping the expensive work. That is the entire bargain.

Many languages let you wrap a function so this happens automatically. Python has a decorator for it in its standard library, functools.cache, and JavaScript libraries offer similar helpers. Writing it by hand once is the best way to understand it, and it takes about five lines.

A simple example: memoizing Fibonacci

The classic example is the Fibonacci sequence. Each number is the sum of the two before it, so fib(n) equals fib(n-1) plus fib(n-2), with fib(0) as 0 and fib(1) as 1.

The plain recursive version looks neat, but it repeats itself badly. To get fib(5), it calls fib(4) and fib(3). But fib(4) also calls fib(3), and both of those call fib(2), and so on. Counting every call, fib(5) makes 15 calls to produce six distinct values.

The waste grows fast. The call count roughly multiplies by 1.6 each time n goes up by one. For fib(40) the plain version makes more than 330 million calls. Most of them recompute something already known.

The same fib(5) with and without a cache.

Now add memoization. Before computing fib(n), check whether n is in cache. If it is, return it. If not, compute it from fib(n-1) and fib(n-2), store it, and return it. Each value from 2 up to n is now computed exactly once. The work drops from exponential growth to a straight line: about n steps. The call that needed 330 million calls now needs about 40 real computations.

Memoization vs caching vs dynamic programming

These three terms overlap, and people mix them up.

• Caching is the general idea of keeping data close so it is quick to reach again. A CPU cache, a browser cache and a database cache are all caching. Caches can hold anything, and they often expire or evict old entries.
• Memoization is a specific kind of caching: it saves the return values of a function, keyed by the arguments. If you can describe it as "remember what this function returned for this input," it is memoization.
• Dynamic programming is a way of designing an algorithm by splitting a problem into overlapping smaller problems and solving each once. You can do it top down, which is memoized recursion, or bottom up, which fills a table in order with no recursion at all.

So memoization is one tool, and dynamic programming is one of the places you use it. The Fibonacci example above is both: a recursive problem with overlapping subproblems, solved once each.

When memoization helps (and when it does not)

Memoization pays off when three things are true.

• The function is pure, so the same input always gives the same answer.
• The function is expensive compared with a dictionary lookup.
• The same inputs really do come up again and again.

Recursive problems with overlapping subproblems are the best fit. Examples include counting paths through a grid, finding the cheapest way to make change, or comparing two strings for their longest shared part. Expensive parsing or formatting of the same values is another good fit.

It does little for these cases:

• A function that is already cheap. The lookup may cost as much as the work.
• A function whose inputs almost never repeat. You fill the cache and never read from it.
• A function with side effects, such as writing a file or sending a request. A saved result would skip the side effect.
• A function that depends on hidden state, like the current time or a global setting.

A quick test: add a counter that tracks cache hits and misses. If hits stay near zero, remove the memoization.

Memoization in game development

Games run the same code many times per second, so remembering answers can matter. Tank City Zero Day, one of the two browser games on our site, shows the idea in two places. Neither one is memoization of a function in the strict sense. Both follow the same rule: keep the finished answer, and rebuild it only when its input changes.

The first is the route map. Enemy tanks need to know the way to the core, going around silicon and coolant, with firewall costing extra because a tank has to shoot through it first. Working that out for every tile is a search, and a search costs far more than a lookup. So the game builds the map once and keeps it. It marks the map as stale when a wall breaks or a wave begins, and it rebuilds it then, no more than five times a second. Between those moments the layout has not changed, so the saved map is still right.

The second is drawing. The game keeps a finished picture of the board and redraws it only when something marks it changed, such as a wall breaking, plus five times a second when the stage has water in it. The same rule applies: do not repeat work whose inputs have not changed.

Level building uses a related trick of a different kind. Each wave's 13 by 13 arena comes from a seed, and the same seed and wave always give the same arena. That is the "same input, same output" property that makes memoization safe, and it is what we describe in how games make sure a level can be beaten.

The first game even teaches the hardware side, and our post on how a CPU cache works goes deeper. In its CACHE stage, the opening fact reads: "A CPU cache keeps recently used data next to the core, because main memory is much slower to reach." Memoization is the same trade done in software.

Common mistakes and tradeoffs

• Memoizing impure functions. If the result depends on anything besides the arguments, the cache will return stale answers. This is the most common bug.
• Unbounded growth. A cache that never forgets eats memory. In a long-running program, set a size limit or evict old entries, for example the least recently used one.
• Bad keys. Keys must compare equal when inputs are equal. Passing a mutable list or object as an argument can break lookups or change the key after you store it. Convert inputs to something stable first.
• Deep recursion. Memoized recursion still uses the call stack. A very deep input can overflow it. The bottom-up table version avoids that.
• Optimizing too early. Measure first. If a function takes microseconds, memoizing it adds code and risk for no gain.

Frequently asked questions

What is memoization in simple terms?

It is a way to save a function's answers so it never works out the same one twice. The function checks its saved answers first and only computes when it finds none.

Is memoization the same as caching?

Not quite. Caching is the broad idea of keeping data handy. Memoization is caching applied to a function's return values, keyed by its arguments.

Does memoization use more memory?

Yes. You spend memory on stored results to save time. If the cache can grow without limit, cap its size or evict old entries.

When should I not use memoization?

Skip it for functions with side effects, functions that read changing state, and functions that are already cheap. Also skip it when the same inputs rarely repeat.

Get started

The best way to feel the idea is to write it. Take the plain recursive fib, add a counter for calls, then add a cache and compare the counts for n equal to 30.

If you want a break that still teaches a little computing, try our two free tank games. Tank City Reboot opens with a true fact about how computers work at the start of each stage, and Tank City Zero Day adds upgrades named for real computer ideas, including Cache and Multithreading.

Play Tank City Reboot: it is free, plays in your browser on a computer or a phone, and needs no account.