Memoization in JavaScript

Introduction to Memoization in JavaScript

Memoization is a powerful technique that can significantly boost the efficiency of your JavaScript code. Imagine being able to store and reuse the results of expensive function calls(that involve heavy or time-consuming calculations) to avoid redundant computations. That’s precisely what memoization allows you to do.

Technically, memoization is a programming technique used to optimise functions by caching their results based on their input arguments.

Example: Consider a simple function to calculate the factorial of a number:

function factorial(n) {
  if (n === 0 || n === 1) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

Without memoization, calling factorial(5) will result in a series of recursive calculations. With memoization, we can store previously computed factorials to avoid redundant calculations.

How Does Memoization Work?

Memoization works by maintaining a cache (typically an object or data structure) that stores the results of function calls. When a function is invoked, it first checks the cache for a previously computed result. If the result exists in the cache, it’s returned; otherwise, the function computes the result, stores it in the cache, and returns it.

Example: Here’s a basic memoization example for the factorial function:

function memoizeFactorial() {
  const cache = {};

  return function(n) {
    if (n in cache) {
      return cache[n];
    } else {
      if (n === 0 || n === 1) {
        cache[n] = 1;
      } else {
        cache[n] = n * memoizeFactorial()(n - 1);
      }
      return cache[n];
    }
  };
}

const factorial = memoizeFactorial();

console.log(factorial(5)); // Returns 120 (computed and cached)
console.log(factorial(6)); // Returns 720 (computed and cached)

How memoization works in JavaScript with the help of closures and higher-order functions, along with examples for each concept:

Closures: Closures are a fundamental concept in JavaScript that allows a function to remember and access variables from its outer (enclosing) scope, even after that outer function has finished executing. This property makes closures a crucial aspect of implementing memoization.

Example:

Consider a simple memoization function for calculating factorials using closures:

function memoizeFactorial() {
  const cache = {};

  return function(n) {
    if (n in cache) {
      return cache[n];
    } else {
      if (n === 0 || n === 1) {
        cache[n] = 1;
      } else {
        cache[n] = n * memoizeFactorial()(n - 1);
      }
      return cache[n];
    }
  };
}

const factorial = memoizeFactorial();

console.log(factorial(5)); // Returns 120 (computed and cached)
console.log(factorial(6)); // Returns 720 (computed and cached)

In this example:

• memoizeFactorial is a higher-order function that returns an inner function.
• The cache variable is captured by the inner function, creating a closure.
• The inner function, when called with an argument n, checks the cache for a cached result or computes and caches it if not found.

Higher-Order Function: A higher-order function is a function that takes one or more functions as arguments or returns a function as its result. In the context of memoization, the memoization function itself is a higher-order function because it returns a function for caching and computing results.

Example:

Expanding on the previous example, here’s how memoization using a higher-order function works:

function memoize(fn) {
  const cache = {};

  return function(...args) {
    const key = JSON.stringify(args); // Generate a unique key based on function arguments
    if (key in cache) {
      return cache[key];
    } else {
      const result = fn(...args);
      cache[key] = result;
      return result;
    }
  };
}

function factorial(n) {
  if (n === 0 || n === 1) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

const memoizedFactorial = memoize(factorial);

console.log(memoizedFactorial(5)); // Returns 120 (computed and cached)
console.log(memoizedFactorial(6)); // Returns 720 (computed and cached)

In this example:

• memoize is a higher-order function that takes a function fn as an argument and returns a memoized version of fn.
• The inner function generated by memoize captures the cache variable and becomes responsible for caching and computing results.
• The unique key for each set of function arguments is generated using JSON.stringify(args) to ensure proper caching.

These examples demonstrate how closures and higher-order functions come together to implement memoization in JavaScript. Closures allow inner functions to access and maintain their own private cache, while higher-order functions make it convenient to create memoized versions of existing functions. This combination results in more efficient and optimised code execution.