Memoization

Memoization in JavaScript is a technique used to optimize the performance of functions by storing the results of expensive function calls and returning the cached result when the same inputs occur again. It is particularly useful in scenarios where the same computations are repeated multiple times, like recursive algorithms (e.g., Fibonacci sequence, factorials, dynamic programming problems).

How Memoization Works:

A cache (often an object or map) is used to store the results of function calls. When the function is called, it first checks if the result for the given input is already in the cache. If it’s cached, the result is returned from the cache, avoiding the computation. If it’s not cached, the function computes the result, stores it in the cache, and then returns the result.

Without Memoization:

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(10)); // 55

This implementation works, but it recalculates the Fibonacci sequence multiple times, resulting in exponential time complexity O(2^n).

With Memoization

function fibonacciMemoized() {
  const cache = {};  // Cache object to store results

  function fib(n) {
    if (n <= 1) return n;
    if (cache[n]) return cache[n];  // Return cached result if available
    cache[n] = fib(n - 1) + fib(n - 2);  // Store the computed result
    return cache[n];
  }

  return fib;
}

const fib = fibonacciMemoized();
console.log(fib(10)); // 55

This reduces the time complexity to linear O(n).

General Memoization Function

function memoize(fn) {
  const cache = {};
  return function(...args) {
    const key = JSON.stringify(args);  // Serialize the arguments as a key
    if (cache[key]) return cache[key];  // Return cached result
    const result = fn(...args);  // Compute result if not cached
    cache[key] = result;  // Store result in cache
    return result;
  };
}

// Example usage with a slow function
function slowFunction(x) {
  console.log('Computing...');
  return x * 2;
}

const memoizedSlowFunction = memoize(slowFunction);
console.log(memoizedSlowFunction(5)); // Computes: 10
console.log(memoizedSlowFunction(5)); // Fetches from cache: 10

Benefits of Memoization:

• Performance optimization: Memoization can drastically reduce the runtime of functions that perform expensive or repetitive computations.
• Avoids redundant calculations: By caching results, it prevents recalculating the same inputs multiple times