Interview Cake by Aced

Memoization

In short: Memoization is an optimization technique that caches a function's results by its inputs, so calling it again with the same inputs returns the saved answer instead of recomputing it. It's the top-down way to do dynamic programming; tabulation (bottom-up) is the other.

Memoization is an optimization technique that ensures a function doesn't run for the same inputs more than once by keeping a record of the results for the given inputs (usually in a dictionary). When the function gets called again with inputs it's already seen, it returns the saved result instead of recomputing it.

For example, a simple recursive function for computing the nth Fibonacci number:

def fib(n): if n < 0: raise IndexError( 'Index was negative. ' 'No such thing as a negative index in a series.' ) elif n in [0, 1]: # Base cases return n print "computing fib(%i)" % n return fib(n - 1) + fib(n - 2)

Will run on the same inputs multiple times:

>>> fib(5) computing fib(5) computing fib(4) computing fib(3) computing fib(2) computing fib(2) computing fib(3) computing fib(2) 5

We can imagine the recursive calls of this function as a tree, where the two children of a node are the two recursive calls it makes. We can see that the tree quickly branches out of control:

A binary tree showing the recursive calls of calling fib of 5. Every fib of n call calls fib of n minus 1 and fib of n minus 2. So calling fib of 5 calls fib of 4 and fib of 3, which keep calling fib of lower numbers until reaching the base cases fib of 1 or fib of 0.

To avoid the duplicate work caused by the branching, we can wrap the function in a class with an attribute, memo, that maps inputs to outputs. Then we simply

  1. check memo to see if we can avoid computing the answer for any given input, and
  2. save the results of any calculations to memo.
class Fibber(object): def __init__(self): self.memo = {} def fib(self, n): if n < 0: raise IndexError( 'Index was negative. ' 'No such thing as a negative index in a series.' ) # Base cases if n in [0, 1]: return n # See if we've already calculated this if n in self.memo: print "grabbing memo[%i]" % n return self.memo[n] print "computing fib(%i)" % n result = self.fib(n - 1) + self.fib(n - 2) # Memoize self.memo[n] = result return result

We save a bunch of calls by checking the memo:

>>> Fibber().fib(5) computing fib(5) computing fib(4) computing fib(3) computing fib(2) grabbing memo[2] grabbing memo[3] 5

Now in our recurrence tree, no node appears more than twice:

A binary tree showing the memos and recursive calls of calling fib of 5. Starting with the calls for fib of n minus 1, fib of 5 calls fib of 4, which calls fib of 3, which calls fib of 2, which calls fib of 1. then, for the fib of n minus 2 calls, fib of 5 gets the memo fib of 3, fib of 4 gets the memo fib of 2, fib of 3 gets the memo fib of 1, and fib of 2 calls fib of 0.

That takes us from exponential time down to linear time:

Computing the nth Fibonacci number Time Space
Plain recursion O(2^n) O(n) for the call stack
Recursion with memoization O(n) O(n) for the memo and the call stack
Bottom-up, keeping just the last two numbers O(n) O(1)

Memoization is a common strategy for dynamic programming problems, which are problems where the solution is composed of solutions to the same problem with smaller inputs (as with the Fibonacci problem, above). The other common strategy for dynamic programming problems is going bottom-up, which is usually cleaner and often more efficient.

Memoization vs. Tabulation (Bottom-Up)

Going bottom-up is also called tabulation, since it usually fills in a table of answers to subproblems, starting from the smallest. Memoization is the top-down approach. Both are ways to do dynamic programming—they just tackle the subproblems in opposite directions:

Memoization (top-down) Tabulation (bottom-up)
Direction Starts from the full problem and recurses down to the base cases Starts from the base cases and builds up to the full problem
How it's written Recursion plus a cache A loop that fills in a table (often a list)
Which subproblems get solved Only the ones the recursion actually reaches Usually all of them, in order
Extra space The memo, plus a call stack that can get deep enough to overflow on big inputs Just the table, and you can often shrink it (like keeping only the last two Fibonacci numbers)
Easier when The recursive solution is natural and you just want to stop repeating work You can see the order the subproblems need to be solved in

In an interview, a good approach is to write the recursive solution, add memoization to speed it up, and then (if there's time) convert it to a bottom-up solution to save space.

See also:

Frequently Asked Questions

What is memoization?

Memoization is an optimization that stores the results of expensive function calls and returns the cached result whenever the same inputs occur again.

What's the difference between memoization and dynamic programming?

Dynamic programming is the general strategy of solving a problem by combining the solutions to overlapping subproblems, solving each one only once. Memoization is one way to do it (top-down: recursion plus a cache); tabulation is the other (bottom-up: filling in a table iteratively).

What's the difference between memoization and tabulation?

Memoization is top-down: it starts from the full problem, recurses, and caches results, so it only solves the subproblems it actually needs. Tabulation is bottom-up: it starts from the base cases and fills in a table with a loop, which avoids recursion and often lets you use less space.

When should you use memoization?

When a recursive function repeatedly solves the same subproblems—like Fibonacci or many DP problems—memoization turns exponential work into linear or polynomial time.

Last updated: October 21, 2026

. . .