24.2.6. Memoized Fibonacci Implementation

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.

The Fibonacci sequence begins with the numbers 0 and 1. Subsequent numbers in the series are created by adding the two numbers that come before it. So, the third Fibonacci number is 1 (0 + 1), the fourth is 2 (1 + 1), the fifth is 3 (1 + 2), and so on. This pattern continues indefinitely and creates a sequence of numbers.

Think of the Fibonacci sequence like a team of friends who each keep adding to a group project based on the contributions of the previous two members. The first two members (0 and 1) start off the project, and every new member builds upon the work done by the last two members.

So, how does the definition of the function code? Fibonacci of n is just if n is 0, return 0, if n is 1 return 1. So, if n is 0 or 1, the value is n itself. Otherwise, you compute value recursively using this criterion Fibonacci of n minus 1 plus Fibonacci of n minus 2.

The Fibonacci function is defined recursively. If you call Fibonacci with 0, it returns 0. If you call it with 1, it returns 1. For any other number n, the function calls itself to get the values for n-1 and n-2, then sums them together. This means every time you want to calculate Fibonacci(n), it may lead to multiple further calculations.

Imagine you're at a party trying to find out the total snacks available based on contributions. If two friends brought snacks, you just need to ask them how many they brought (the base cases). For any larger number of friends inviting snacks, you ask the previous two friends how many snacks they brought to calculate the total.

So, the problem we can see is that functions that Fibonacci of 3 have been computed twice in full and full complexity, other functions like Fibonacci of 2 have been computed 1, 2, 3 times and so on.

The recursive approach leads to redundant calculations. For example, Fibonacci(3) is calculated multiple times when you compute Fibonacci(5). Similarly, Fibonacci(2) is also recalculated unnecessarily, leading to inefficiencies. This means that as n grows, the number of operations grows exponentially due to repeated calculations.

Think about asking two friends about who invited whom to a movie multiple times when you could just write down the answer once. Repeatedly asking results in the same answers, leading to wasted time for both you and your friends.

So, 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 and what does the table do? It just keeps track of every value for which you have computed the function before.

Memoization is a technique to store the results of expensive function calls and reuse them when the same inputs occur again. Instead of recalculating Fibonacci(3), you check the table to see if the value has already been computed and stored, saving time and computational resources.

It's like keeping a folder of notes where you write down each friend's contributions to the snack party. When asked about a certain friend's contribution, you simply look at your notes instead of asking them each time, thereby saving time.

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 as we compute them. ... So, now that I have computed Fibonacci of 4, I can also compute Fibonacci of 5 using the values stored.

In practical terms, a memo table is maintained where every calculated Fibonacci number is stored. When calculating Fibonacci(5), say you need Fibonacci(4) and Fibonacci(3). You compute Fibonacci(4) and store the result before computing Fibonacci(3) next. If Fibonacci(3) is needed again, you simply look it up in the table and retrieve the value instead of recalculating it.

This is similar to how you would use a calculator to solve math problems. After solving a complex equation, you would store the answer. If someone later asks for that answer again, you can provide it instantly rather than recalculating the entire equation.

What you can see in this is that the computation tree which used be exponential is now linear. ... So, every new value that we compute, we store in the table that could be able to use it again or not we do not know, but if we want to use it again, it is good to have it there.

Memoization dramatically reduces the time complexity of calculating Fibonacci numbers from exponential to linear. This is because once a value is computed, it is stored in the memo table, and future calls for that value are served immediately without the need for further calculations.

Imagine an extensive library where every book you read is listed in a log. The next time you want to read about a specific topic, instead of searching through the entire collection again, you just check your log for the title, thus saving you immense time and effort.

--