Memoization in JavaScript

Memoization is an optimization technique that we use to cache results of expensive computations to avoid recalculating previously processed inputs.

Expensive computations, refer to the Time Complexity that a given algorithm will take to complete. The "cost" of an algorithm is represented using Big O Notation.

A memoized function "remembers" the results corresponding to some set of specific inputs and returns the cache result.

---

Why memoization is important?

Memoization is important because it makes our programs faster by caching results of function calls and avoiding redundant computations. If a function is called again with the same arguments as before, the stored results will be returned, rather than running the function again. This reduces execution time and improves performance in our programs.

Practical example

The fibonacci algorithm is a great usecase to explore a practical example of how we can use memoization to speed up our programs.

The Fibonacci sequence is a series of numbers. The first two numbers of the sequence are 0 and 1, and every number after that is the sum of the previous two numbers.

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

The fibonacci algorithm will take one number as a parameter(position), and it'll return the number that belongs in that position in the Fibonacci sequence.

Example:

fibonacci(4) // returns 3
fibonacci(2) // returns 1
fibonacci(8) // returns 21

Recursive Solution

A recursion function is when the function calls itself until a base case is met. Similar to how the for or while loops work.

A base case is a condition that stops the recursion.

• For the fibonacci sequence, the base case is num < 2.
• If the base case is true it will exit the loop.
• Else the recursion will enter a loop calling itself.

const fibonacci = num => {
  if (num < 2) {
    return num
  }
  return fibonacci(num - 1) + fibonacci(num - 2)
}

fib(8) // returns 21 and it's call 6765 times!!

While this solution certainly works. The time complexity is O(2^N) or exponential time. We want to avoid Exponential running time at all cost. If we try to run this fibonacci function with a number greater than 40 our computer will freeze.

Memoization can help us improve time complexity.

Memoized function

Let's create a generic memoize function to avoid recalculating previously processed inputs. We'll be able to use our generic memoize function with the fibonacci algorithm.

Generic Memoize Function

• Create an object to cache previously processed inputs.
• Pass a function (fn) to memoize.
• Return early if the proccessed value is already stored in cache.
• Accept a flexible number of arguments (args) using the spread operator.
• Use apply to invoke the passed function as it doesn't exist in cache.
• Return the result.

const memoize = fn => {
  const cache = {}
  return function (...args) {
    if (cache[args]) {
      return cache[args]
    }
    const result = fn.apply(this, args)
    cache[args] = result
    return result
  }
}

This is how we use could use the memoize function. Note, we are calling the memoize function(fib), not "fibonacci". This makes our time complexity O(N) or constant time, dramatically improving the performance of our function.

const fibonacci = num => {
  if (num < 2) {
    return num
  }
  return fib(num - 1) + fib(num - 2)
}

const fib = memoize(fibonacci)
fib(8) // returns 21 and it's call 19 times.

---

Alternative memoize solution

In this example, we are using the same memoization principles as in our generic function, but inside the function that we want to memoize.

function fibonacciMemo() {
  let cache = {}
  return function fib(n) {
    if (cache[n]) {
      return cache[n]
    }
    if (n < 2) {
      return n
    }
    cache[n] = fib(n - 1) + fib(n - 2)
    return cache[n]
  }
}
const fib = fibonacciMemo()
fib(20) // returns 21 and it's call 19 times.

---

Conclusion

Memoization is a chaching technique that will improve performance optimization. Keep an eye on recursive code to Memoized redundant computations. Exponential running time O(2^N) is extremely slow and we should avoid it at all cost.