Memoizing the Recursive Algorithm
00:00 Memoizing the Recursive Algorithm. As you saw in the code earlier on, the Fibonacci function calls itself several times with the same input. Instead of a new call every time, you can store the results of previous calls in something like a memory cache.
00:28 Memoization speeds up the execution of expensive recursive functions by storing previously calculated results in a cache. This way, when the same input occurs again, the function just has to look up the corresponding result and return it without having to run the computation again.
00:45 You can refer to these results as cached or memoized. With memoization, you just have to traverse up the call tree of depth N once after returning from the base case, as you retrieve all the previously calculated values highlighted in yellow, F(2) and F(3), from the cache earlier.
01:04 The orange path shows that no input to the Fibonacci function is called more than once. This significantly reduces the time complexity of the algorithm from exponential to linear. Even for the base cases, you can replace calling F(0) and F(1) with just retrieving the values directly from the cache indices zero and one.
Initially, the cache contains the starting values of the Fibonacci sequence,
1. Inside the function, you first check if the Fibonacci number for the current input is already in the cache. If so, then you return that number.
Become a Member to join the conversation.