24.2.4. Memoization Technique

Let us continue our discussion of inductive definitions. (Refer Slide Time: 00:05) 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.

In this first chunk, we revisit the concept of inductive definitions and their importance in programming, especially in recursion. Inductive definitions, such as those for factorial and sorting algorithms, break problems down into simpler sub-problems that the main function can then solve using recursion. This approach makes it intuitive to write recursive programs.

Imagine you want to bake a cake, and you have a recipe. The recipe breaks down the entire process into smaller tasks: mixing the batter, preheating the oven, baking, and cooling. Each of these tasks can be viewed as a sub-problem of the greater task (baking the cake), just as functions split complex computations into manageable parts.

But, the challenges is, in identifying the sub problems, I am making sure that they are not overlapped. So, in the case of factorial remember that any smaller input factorial is a sub problem, similarly for sorting you can think of any segment of the list to be sorted as a sub problem.

This chunk highlights a key challenge in implementing recursive solutions: ensuring that the subproblems involved do not overlap. If a subproblem, such as calculating a factorial, is called multiple times during the recursive process, it leads to unnecessary computations, increasing time complexity.

Consider solving a puzzle where you need to fit pieces together. If you try to fit the same piece in the same spot repeatedly, you waste time and effort. Each attempt won't yield a different result. Instead, recognizing that certain pieces fit into specific places helps streamline the puzzle-solving process, mirroring how avoiding repeated calculations in recursion streamlines program execution.

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.

In this chunk, Fibonacci numbers are introduced as a classic example of an inductive definition. The sequence starts with 0 and 1, and each subsequent number is the sum of the two preceding ones, forming a simple recursive relationship. It sets the stage for exploring how recursion functions in practice.

Think of Fibonacci numbers like a family tree: each number (generation) stems from combining the two prior generations (parents), illustrating how growth and connection build up in nature and many phenomena.

So, the problem we can see is that functions that Fibonacci of 3 have been computed twice in full and full complexity...

This chunk explains the issue of recalculating Fibonacci numbers multiple times due to the recursive algorithm's structure. While computing Fibonacci(5), the algorithm may compute Fibonacci(3) and Fibonacci(2) multiple times, leading to exponential growth in computational steps rather than linear. This inefficiency is a prime reason for needing techniques like memoization.

Imagine trying to find the best route for a road trip, but you're repeatedly checking directions to landmarks you already passed. Each redundant calculation wastes time, just as unnecessary recursive calls waste computational resources in the Fibonacci calculation.

One way to get around this is to make sure that you never reevaluate a sub problem. So, you build up a table which is sometimes called a memory table...

This chunk introduces the concept of memoization: a technique to enhance the efficiency of recursive functions by storing the results of subproblems in a table. Before recalculating a value, the algorithm checks this table to see if it has already computed the value, thereby saving time.

Think of memoization like a bookmark in a book. Instead of rereading pages you've already covered, you mark your place so you can quickly return to it later. This technique helps ensure you don’t spend time revisiting the same information unnecessarily.

So, how does memoization work? So, we have this memo table here, so this is our memo table, so in this memo table it is just a table where we fit different value of k and fib k has we compute them...

This chunk delves into the practical implementation of memoization, exemplified through a memo table for Fibonacci numbers. Each time a Fibonacci number is calculated for the first time, it is stored in the memo table, allowing subsequent calls to check this table for already computed values. This transition transforms an exponential time algorithm into a linear one.

Consider using a reservation system at a restaurant. Instead of checking availability for each table every time, the system keeps track of which tables are available. If someone asks about a table, it quickly checks the records rather than looking through every detail each time.

Why is it linear? Because, every value which is in blue appears in the 1s and every value which in not in blue is a look up in the table...

Here, we conclude the memoization discussion. When memoization is applied, each Fibonacci number is calculated just once and stored, meaning repeated calls for the same number can fetch directly from the memo table. This efficiency cuts the work from exponential to linear time, greatly improving performance.

Imagine writing a report. Instead of rewriting the same information from scratch multiple times, you keep all your references organized in a notebook. When you need a piece of information, you quickly find it rather than searching through all your sources again.

--