24.2.7. Generic Memoization

Fibonacci numbers are defined such that the first two Fibonacci numbers are 0 and 1, and every subsequent Fibonacci number is the sum of the two preceding ones.

The sequence begins: 0, 1, 1, 2, 3, 5, 8, 13, ...

The Fibonacci sequence starts with the numbers 0 and 1. Next, each number is created by adding the two previous numbers, resulting in a pattern that directly builds upon prior values. For instance:

• The 3rd Fibonacci number (1) is the sum of the 1st (0) and 2nd (1).
• The 4th Fibonacci number (2) is the sum of the 2nd (1) and 3rd (1).
• Continuing this way, you get a growing sequence of values: 0, 1, 1, 2, 3, 5, 8, and so forth.

Think of the Fibonacci sequence as building blocks where each block depends on the two blocks before it. You start with two foundational blocks (0 and 1), and every time you want to build a new level, you stack the previous two blocks together to create a new one.

The function to compute the nth Fibonacci number can be defined recursively:

Fibonacci(n) {
  if n == 0;
    return 0;
  if n == 1;
    return 1;
  return Fibonacci(n-1) + Fibonacci(n-2);
}

The recursive function follows a simple structure:

1. It checks if n is 0. If true, it returns 0.
2. It checks if n is 1. If true, it returns 1.
3. For values greater than 1, it calls itself to calculate Fibonacci(n-1) and Fibonacci(n-2), summing these results to find the nth Fibonacci number. Although this method is straightforward, it can lead to redundant calculations.

Imagine you are climbing stairs, where the number of ways to get to the nth step equals the total ways to get to the (n-1)th and (n-2)th steps. This means to get to step 3, you can get there from step 2 or step 1, representing how recursive functions branch out to find results.

When calculating Fibonacci(5), the recursion creates multiple calls leading to repeated calculations:

• Fibonacci(5) calls for Fibonacci(4) and Fibonacci(3).
• Fibonacci(4) wants Fibonacci(3) and Fibonacci(2), and so on, resulting in the same values calculated multiple times.

The recursive calls demonstrate overlapping subproblems. For example, Fibonacci(3) is computed multiple times through different paths in the recursion tree, leading to inefficiency. This redundancy increases the total computational complexity exponentially, making it slow for larger inputs.

Picture trying to find a path in a maze. If you reach a dead end (a Fibonacci calculation you've already made), you might go back and retrace your steps to check the same route again and again. It wastes time instead of using your memory of where you’ve already been.

To solve the redundant calculations, memoization involves storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Memoization creates a 'memory' for the function results, effectively building a table that stores what has already been computed. For each Fibonacci call, before calculating, the function checks if the result is already in the table. If it is, it retrieves the value, saving the computational effort of recalculating.

Think of memoization as writing down the answers to math problems in a notebook. Next time you encounter the same problem, instead of calculating it again, you simply flip to the page and read the answer. This saves you time and effort.

With memoization, the Fibonacci function checks a memo table before computing values:

if fib_table[n] is not None:
  return fib_table[n]
else:
  # compute Fibonacci value and store it in the table
  fib_table[n] = Fibonacci(n-1) + Fibonacci(n-2)
  return fib_table[n]

This code snippet shows how a memo table is integrated into the Fibonacci function. It first checks if the value for a given n is already in the table. If so, it returns that value immediately. Otherwise, it computes the Fibonacci value, stores it in the table for future calls, and returns the newly computed value.

Using the math notebook analogy, checking the notebook before solving a problem represents memoization. If you have previously solved the problem, your notebook tells you the answer right away without needing to do the math again.

Using memoization improves the efficiency of the recursive functions significantly:

• The complexity is reduced from exponential to linear time.
• Each Fibonacci number gets computed just once.

The key advantage of memoization is that it eliminates redundant calculations. With memoizing Fibonacci, each unique Fibonacci calculation is performed only once, transforming the overall complexity from exponential (which grows very fast) to linear, which is manageable even for larger inputs.

Consider a factory using memos to avoid redundant steps in production. Instead of repeating the same task (calculating Fibonacci values), they streamline the process, significantly speeding up production and reducing waste.

--