Implementing Memoized Fibonacci in JavaScript

25 Apr 2021 •

In this article, we will explore how to optimize the Fibonacci sequence algorithm using Memoization.

A standard recursive implementation of the Fibonacci sequence is notoriously inefficient due to repeated calculations. Memoization allows us to store the results of expensive function calls and return the cached result when the same inputs occur again.

---

The Problem: Classical Implementation

Let’s look at the standard recursive approach first:

function fibonacci(position) {
  if (position < 3) return 1;
  else {
    return fibonacci(position - 1) + fibonacci(position - 2);
    // Returns the sum of the previous two numbers
  }
}

fibonacci(6); // Returns 8

Why is this slow? The time complexity of this algorithm is roughly O(2^n) (Exponential Time). For every call, it branches into two more calls. If you try to calculate fibonacci(50), your browser might freeze because it has to perform billions of operations.

---

The Solution: Memoization

We can improve this performance dramatically to O(n) (Linear Time) by passing a cache (an array) to store values we’ve already calculated.

Here is the memoized implementation:

function fibMemo(index, cache) {
  // Initialize cache if it doesn't exist
  cache = cache || [];
  
  // 1. Check if value exists in cache
  if (cache[index]) {
    return cache[index];
  }
  
  // 2. Base case: The first two numbers are 1
  else {
    if (index < 3) return 1;
    else {
      // 3. Recursive step: Calculate and store inside the cache
      cache[index] = fibMemo(index - 1, cache) + fibMemo(index - 2, cache);
    }
  }

  // 4. Return the calculated value
  return cache[index];
}

// Example usage
fibMemo(100); // 354224848179262000000

How it works

1. Cache arguments: The function takes an index and a cache array. If current cache is empty or undefined, we initialize it as an empty array.
2. Check Cache: Before doing any calculation, we check if (cache[index]). If we have already calculated the Fibonacci number for this index, we return it immediately.
3. Recursive Calculation: If the value isn’t in the cache, we calculate it using the standard formula fib(n-1) + fib(n-2). Crucially, we pass the same cache array down to these recursive calls.
4. Store Result: Once calculated, we save the result into cache[index] so we never have to calculate it again.

The Advantage

With the classical implementation, calculating the 50th Fibonacci number might take minutes (or crash). With the memoized version, we can calculate fibMemo(1000) instantly because we only calculate each number exactly once.