Understanding Memoization in JavaScript

Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and reusing them when the same inputs occur again.

How Does Memoization Work?

Here's a simple example of a memoized function:

function memoize(fn) {
  const cache = {}
  return function (...args) {
    const key = JSON.stringify(args)
    if (cache[key]) {
      return cache[key]
    } else {
      const result = fn(...args)
      cache[key] = result
      return result
    }
  }
}

In the above example, memoize is a higher-order function that takes a function fn as an argument and returns a new function. This new function checks if the result for the given arguments is in the cache. If it is, it returns the cached result. If it's not, it calls fn, stores the result in the cache, and returns the result.

Applying Memoization to the Fibonacci Sequence

The Fibonacci sequence is a classic example of a function that can benefit from memoization due to its recursive nature. Here's how you can apply memoization to the Fibonacci sequence:

function fibonacci(n, fn) {
  if (n < 2) {
    return n
  } else {
    return fn(n - 1) + fn(n - 2)
  }
}

const simpleFibonacci = (n) => fibonacci(n, simpleFibonacci)
const memoizedFibonacci = memoize((n) => fibonacci(n, memoizedFibonacci))
const FIBONACCI_NUM = 38

console.time('Non-memoized Fibonacci')
console.log(simpleFibonacci(FIBONACCI_NUM)) // First call, result is computed
console.timeEnd('Non-memoized Fibonacci')

console.time('Memoized Fibonacci')
console.log(memoizedFibonacci(FIBONACCI_NUM)) // First call, result is computed
console.timeEnd('Memoized Fibonacci')

You can see a working example of this code on StackBlitz. To run the code, open the terminal in StackBlitz and type node index.

When you run this code, you should see the following output in your console:

39088169
Non-memoized Fibonacci: 497ms
39088169
Memoized Fibonacci: 0.6ms

This output demonstrates the significant performance improvement that memoization can provide. The non-memoized Fibonacci function took 497 milliseconds to compute the 38th Fibonacci number, while the memoized version took only 0.6 milliseconds to compute the same result.

Why Use Memoization?

Memoization can significantly speed up your JavaScript applications by avoiding expensive computations and optimizing function calls. It's especially useful when dealing with recursive functions, complex calculations, and operations that are called repeatedly with the same inputs.

Understanding memoization can help you write more efficient and performant JavaScript code.