Memoized Fibonacci function in JavaScript

25 Apr 2021 2 mins

Let’s implement the memoized fibonacci function using JavaScript. Memoized function store previously calculated values for the particular argument in cache or hash. When we call the function recursively with previously calculated index as an argument to our function,it looks into cache first and used it to save extensive calculation.

With classical implementation, our time complexity of the algorithm will be

// time complexity just for an input 4:

 T(n) = T(n-1) + T(n-2) + C

 T(n) = O(2^(n-1)) + O(2^(n-2)) + O(1) 

At large n, we obtain O(2^n), which is exponential time (slow as molasses).

Where as implementation below outperform O(n)

// fibMemo function takes two argument index and cache. At initial call cache is empty
function fibMemo(index, cache) {
  cache = cache || [];
  // check if we already have a value in a hash
  if (cache[index]) return cache[index];
  // this code will execute if we are calculating
  // it value for initial
  else {
    if (index < 3) return 1;
    else {
      // this is a important statement, if we don't have the
      // value, we pass the existing cache and index to same
      // function which used cache to return us value faster.
      cache[index] = fibMemo(index - 1, cache) + fibMemo(index - 2, cache);
    }
  }

  // finally we return the cache[index].
  return cache[index];
}

// calling
fibMemo(1000);

Above function takes two argument index and cache. Cache is a hash previous cache we have. At initial invocation cache is assume to be empty, but we pass cache value when we call this function recursively.

If we analyzed the function above, we have two termination case for fibMemo function. With out memo recursive function terminate if index is less then 3. But in current implementation if we have cache with desire index terminated by returning the value we have already calculate.

Similarly, each time we when we calculate some value we store value in a cache and pass it to recursive function to shorten the calculation.

Advantage: With this implementation we can calculate fibo series of 1000 or 1200 on the fly. With classical implementation it might take several minutes.

---

Here is the classical implementation:

function fibonacci(position) {
  if (position < 3) return 1;
  else {
    return fibonacci(position - 1) + fibonacci(position - 2);
  }
}

fibonacci(6);