Memoization

Exercise:

What is memoization? What are its benefits? What is the necessary condition for using memoization? Illustrate the benefits of memoization using an example.

Remark:

Expect these types of questions when bridging theory with practice. You need to know what you are doing, and you have to write code that runs properly. The task itself is up to your interpretation, so choose the easiest possible solution.

Solution:

Memoization is an optimization technique often used with recursion. We create a lookup table that contains the mapping between the input and the output of the function. If the input has been calculated before, we find the corresponding output in the lookup table and return it. If the input has not been calculated, we calculate it and insert it into the lookup table.

There are several benefits of memoization. First, if the computation of the return value of a function takes a lot of time, substituting it with a simple lookup saves a lot of time. Second, we may save a lot of recursive calls, as computing the value may imply entering into the same sequence of recursive calls. In general, if we are interested in computing the same value over and over again, we have a case for memoization.

The necessary condition of using memoization is that the function has to be deterministic. This means that the input values should always determine the return value of the function regardless of the external context.

We will use the Fibonacci function to illustrate memoization. The original Fibonacci function can be implemented like this: