24.2.5. How Memoization Works

Let us continue our discussion of inductive definitions. The attraction of looking at inductive definitions is that we can very easily come up with recursive programs that implement them. But, the challenge is in identifying the subproblems and ensuring they are not overlapped.

Memoization is a technique used to optimize the performance of recursive functions by storing previously computed results. This helps in avoiding the re-evaluation of the same subproblems multiple times. The main benefit of memoization is simplifying the problem, making the recursive function more efficient by transforming a potentially exponential time algorithm into a linear time one.

Think of memoization like a recipe box where you store successfully tried recipes. Instead of trying to remember all the steps for your favorite dish every time, you just look it up in your recipe box. Similarly, memoization lets a program 'remember' previously calculated values, so it can access them quickly instead of recalculating them.

Let us see how this works with the Fibonacci numbers. The first two Fibonacci numbers are 0 and 1, and every successive Fibonacci number is obtained by adding the two preceding ones. If we implemented this recursively without memoization, calculating Fibonacci of 5 would require a lot of repeated calculations.

Fibonacci numbers can be computed recursively but with significant overlap in the computations. For instance, to compute Fibonacci(5), we need both Fibonacci(4) and Fibonacci(3), and those results further require Fibonacci(2) and Fibonacci(1) repeatedly, leading to redundant calculations. However, with memoization, once we calculate a Fibonacci number, we store it; if we need that number again, we fetch it from storage instead of recalculating it.

Imagine you’re solving a puzzle and you find that certain pieces connect together. When you need to assemble the same section of the puzzle again, instead of figuring it out from scratch, you can refer to the completed section you saved earlier. This is how memoization can speed up computations.

The core idea is to create a memo table, which keeps track of values already computed. For example, when calculating Fibonacci(5), we would check if Fibonacci(4) and Fibonacci(3) already exist in the table. If they do, we don’t recalculate them.

To implement memoization, you first create an empty table (or dictionary) to hold the computed Fibonacci values. When calculating a Fibonacci number, before executing the recursive calls, you check the table to see if the value has already been computed. If it exists, return that value. If not, compute it using the recursive formula, store the result in the table, and then return that new value.

Think about how a student prepares for exams. Instead of rewriting all notes every time they study, they keep a comprehensive notebook. When studying a topic they’ve covered before, they refer to their notes instead of rewriting everything. In memoization, the memo table serves as the student's notebook of remembered calculations.

With memoization, the computation time to find Fibonacci(5) becomes linear instead of exponential because we only compute the same Fibonacci number a single time.

The computational efficiency gained from memoization is significant because it reduces the number of calculations drastically. Originally, without memoization, the calculations for Fibonacci numbers involve multiple overlapping calls leading to an exponential time complexity. However, with memoization, each unique Fibonacci value is computed once and stored, resulting in a linear relationship between the input size and the number of computations.

Think of a busy restaurant. If a chef has a list of regular orders written down, they can prepare dishes faster instead of asking customers for their orders every time. This is what memoization does for computations—by keeping a record of what’s already been done, it saves time.

--