###### Books / Fundamentals of Computer Science / Chapter 19

# Memoization and Dynamic Programming

The Fibonacci Sequence may be defined recursively by the following formula:

f(0) = 0

f(1) = 1

f(n) = f(n-2) + f(n-1)

for n>1

This leads to a very simple recursive implementation of a method to compute the *n*‘th member of the Fibonacci sequence:

This method is *correct*, in the sense that it will compute the correct result. However, it is not *efficient* because it violates one of the rules of recursion: specifically, it recomputes the answer to subproblems more than once.

Here is the “tree” of recursive calls that will result from calling the **fib** method with the argument 5:

Note that the subproblem fib(3) is computed twice, fib(2) is computed three times, fib(1) is computed 5 times, and fib(0) is computed 3 times. As n increases, the size of the tree (the number of recursive calls required) grows *exponentially*. Exponential functions grow very, very fast; so fast that algorithms with exponential running time are generally intractable, even for relatively small input sizes. In an algorithm with exponential running time, even a small input may require a very large number of steps to solve.

Here is a Java program that computes members of the Fibonacci sequence recursively using the naive approach:

If you try running this program, you will notice that the number of milliseconds required to compute the requested Fibonacci number grows very quickly. On my laptop^{†}, the 40th Fibonacci number takes about 6 seconds to compute, and the 41st takes 9.5 seconds! Here is a graph showing the number of milliseconds required for n=1 to n=41:

^{†} This was written in 2005. A more recent computer would be faster, but the shape of the plot’s curve would be similar.

Obviously, this is not a good implementation of **fib**.

*Memoization* is a technique for avoiding recomputing the answers to subproblems in a recursive algorithm. The idea is very simple: record the answers to subproblems in a table. Each time an answer to a subproblem is needed, consult the table. If no answer exists in the table, perform the computation *and save the answer in the table*. Future occurrences of the subproblem can be “solved” by just loading the answer from the table.

Here is a simple memoized version of the same program. Answers to subproblems are saved in an array called **memo**.

Because each subproblem is computed only once, this version of **fib** has linear (O(n)) running time. As you can see, this memoized implementation is a trivial modification of the naive recursive implementation.

A related technique, called *dynamic programming*, is to start with the smallest subproblem, and then to iteratively work up towards larger problems, until the overall problem is solved. This kind of solution can be written using a loop of the general form

for j = 1 to n memo[j] = solve subproblem j return memo[n]

The step that reads “solve subproblem j” may be implemented by looking up the answers to previously solved subproblems.

Here is a dynamic programming version of the program to compute the *n*‘th Fibonacci number: