Learning JavaScript Data Structures and Algorithms - Third Edition

Fibonacci with memoization

There is also a third approach, called memoization, that we can use to write the fibonacci function. Memoization consists of an optimization technique that stores the values of previous results, similar to a cache. If we analyze the calls made to compute fibonacci(5), we will notice that fibonacci(3) was computed twice, so we can store its result so that when we compute it again, we already have it.

The following code represents the fibonacci function written with memoization:

function fibonacciMemoization(n) {
  const memo = [0, 1]; // {1}
  const fibonacci = (n) => {
    if (memo[n] != null) return memo[n]; // {2}
    return memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo); // {3}
  };
  return fibonacci;
}

In the preceding ...