24.2. Memoization

Let us continue our discussion of inductive definitions.

So, recall that functions like factorial and insertion sort are natural inductive definitions in terms of smaller sub problems. The attraction of looking at inductive definitions is that, we can very easily come up with recursive programs that implement them in a very obvious way. But, the challenges is, in identifying the sub problems, I am making sure that they are not overlapped.

In this chunk, we get introduced to the concept of memoization. It highlights how inductive definitions, such as factorial and insertion sort, allow us to define recursive programs easily. However, a challenge in this approach is identifying overlapping sub-problems, which memoization aims to resolve by avoiding redundant calculations.

Think of it like baking a cake. You might need the same frosting recipe multiple times for different layers of the cake. Instead of recreating the frosting each time, you can make a larger batch and keep it stored, so you can quickly reuse it whenever you need.

So, let us see how this works with the very familiar series that you may know of by Fibonacci numbers. So, let us define the Fibonacci numbers as follows, the first two Fibonacci numbers are 0 and 1 and then every successive Fibonacci number is obtained by adding these two.

Here, the Fibonacci sequence is presented, starting with the base cases: 0 and 1. Each subsequent number is the sum of the previous two, creating a series that grows quickly. Understanding this sequence is crucial because it demonstrates the inductive nature of many recursive functions.

Imagine a rabbit population that starts with one pair. Each month, the rabbits breed and create another pair, while the original pair continues to reproduce. The number of pairs each month follows the Fibonacci sequence—month by month, the population grows in a way that can be calculated based on previous months.

So, where is the catch? So, let us see how this would work on an small input like we have just saw Fibonacci. ... So, the problem we can see is that functions that Fibonacci of 3 have been computed twice in full and full complexity.

This section delves into the recursive calculation of Fibonacci numbers. When calculating Fibonacci(5), the recursive calls lead to duplicating computations, like calculating Fibonacci(3) multiple times. This redundancy results in inefficiency, making the time complexity exponential instead of linear.

Recall the rabbit example: if we don't keep track of how many rabbits were born in the previous months, we might end up recounting later generations multiple times, leading to excess calculations. Efficient tracking (like memoization) would allow us to save the number of rabbits born in previous months so we don’t count them again.

One way to get around this is to make sure that you never reevaluate a sub problem. So, you build up it table which is sometimes called a memory table and what is the table do it just keeps track of every value.

To address the inefficiency found in recursive calculations, memoization can be utilized. By constructing a table that keeps track of previously computed values, this technique prevents the same computations from occurring more than once, thus speeding up the overall process.

Consider a library where instead of checking out the same book multiple times, you record each book checkout in a register. The next time someone wants to borrow that book, you simply refer to the register instead of digging through all the shelves again.

So, how does memoization work? So, we have this memo table here, ... before we computed recursively and if we have to computed recursively, then we will store each newly computed back end of the table.

This chunk explains the practical implementation of memoization. When calculating Fibonacci(5) recursively, now we first check if that value is already in the memo table. If not, we compute it and store the result in the table for future reference, significantly reducing computation time.

It’s like using a calculator for complex math. Once you compute a difficult calculation, you write down the answer. Next time you need that answer, you simply look at your notes instead of solving the problem all over again.

To summarize, we have seen two strategies to make recursive computations of inductive functions more efficient. The first is memoization...

In conclusion, memoization is a powerful technique that makes recursive calculations much more efficient by remembering results of previously computed values. This reduces redundant calculations and saves time when solving problems recursively.

If you’re learning a new language, memorizing vocabulary words and references can save you time. Instead of looking up the same word for the same meaning, you keep a notebook where you write down the meanings, allowing you to quickly refer back without repeated searches.

--