24.2.2. Fibonacci Numbers

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. Now, it is instructed to see even before you begin how we would numerate the Fibonacci numbers. We know that the first two are 0 and 1 and we know the next one is sum of these two. So, the next one will be 1 again, next one will be 2, for this 1 plus 1, next one will be 3, next one will be 5, next one will be 8, next one will be 13 and so on.

The Fibonacci sequence starts with two initial numbers: 0 and 1. From these, each subsequent number is the sum of the two preceding numbers. This pattern continues indefinitely. For example: Starting with 0 and 1: 0, 1. Now, adding these two gives us 1 (0 + 1 = 1). Next, we add 1 (the last Fibonacci number) and 1 (the one before it) which gives us 2. Thus, we have: 0, 1, 1, 2. Continuing this, 1 + 2 = 3, so we now have: 0, 1, 1, 2, 3. Then 2 + 3 gives us 5, 3 + 5 gives us 8, and so on. This infinite series can be easily generated using simple addition.

Think about climbing stairs. Imagine you want to reach the top of a staircase and you can take either 1 stair at a time or 2 stairs at a time. The number of distinct ways to climb to the N-th step can be represented by Fibonacci numbers. For instance, to reach the 4th step (N=4), you can either: 1 + 1 + 1 + 1 (four single steps), 1 + 1 + 2 (two single steps and one double step), or 2 + 2 (two double steps). This illustration shows how the ways to ascend are associated with Fibonacci sequence values.

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 and finally, whatever value you are computed you return.

The Fibonacci function is defined recursively: if you want to find Fibonacci of any number 'n', you check if 'n' is either 0 or 1, which are the base cases. For Fibonacci(0), it returns 0; for Fibonacci(1), it returns 1. For any other number greater than 1, you compute the Fibonacci number as the sum of the two previous Fibonacci numbers: Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2). This recursive nature allows us to break down the problem into smaller, manageable parts.

Imagine you're a teacher giving quizzes to your students. The first quiz has no questions (F(0)=0), and the second quiz has just one question (F(1)=1). For the third quiz (F(2)), you need the result of the first two quizzes combined, which is the total questions from F(1) plus F(0). So you'd aggregate these to get the number of questions in F(2) as 1 (from F(1)) + 0 (from F(0)) = 1. Then for F(3), you'd gather results from F(2) and F(1), and so forth, showcasing how each quiz relies on the knowledge of two prior quizzes.

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 can lead to inefficiency. For example, while calculating Fibonacci(5), the function needs to calculate Fibonacci(4) and Fibonacci(3). However, Fibonacci(3) requires both Fibonacci(2) and Fibonacci(1), and Fibonacci(4) needs to compute Fibonacci(3) again. This leads to multiple redundant calculations of the same Fibonacci numbers. This redundancy causes the overall computation time to grow exponentially with the input size due to the repeated evaluations of the same inputs.

Think of a student trying to solve a problem by submitting the same answer multiple times to the same question. If they repeatedly ask about the answer to a problem, they aren't building upon what they already know. Instead, they're wasting time recalculating the same information rather than using it to progress to the next question. This inefficiency can lead to extended study times, much like how our recursive Fibonacci function takes exponentially longer due to repeated calculations.

One way to get around this is to make sure that you never reevaluate a subproblem. 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 used to optimize the recursive solution. Instead of recalculating the Fibonacci numbers, we store each computed value in a 'memo table'. When computing a Fibonacci number, before performing the recursive calculations, we first check our memo table to see if we have already computed that value. If it exists, we retrieve it from the table; if it does not exist, we compute it, store it in the table, and then use that value in future calculations. This elimination of redundant calculations significantly speeds up the process.

Imagine you are baking cookies and you write down the recipe on a notepad. Each time you want to bake another batch, instead of trying to remember everything from memory and potentially making errors, you simply look at your notes. Your notes serve as a memo table, allowing you to refer to the exact measurements and steps you took before, thereby saving time and ensuring consistency in your baking!

So, what you can see in this is that the computation tree which used to be exponential is now linear.

With the implementation of memoization, the number of calculations significantly decreases. By storing the results of subproblems, we ensure that each Fibonacci number is computed only once. When the Fibonacci function is called, it first checks the memo table. If the value is already computed, it retrieves this value without further calculations, leading to a linear time complexity instead of exponential. This is crucial for efficiency, especially with larger Fibonacci numbers.

Think of a librarian who organizes books in a way that all similar books are grouped together. Once you find a book, the next time you need it, you know exactly where to find it without searching through every single shelf again. This organization allows for quick retrieval and saves time, much like memoization allows quick access to computed Fibonacci values without redoing all the previous work.

--