Optimizing Recursive Functions with Memoization in JavaScript

Recursive functions provide an elegant way to break complex problems into smaller subproblems. However, when subproblems overlap—as in the classic Fibonacci sequence—a naive recursive implementation recalculates the exact same inputs millions of times, resulting in exponential O(2^n) time complexity.

Memoization is an optimization technique where we cache the return value of a pure function in a lookup object (cache) keyed by its arguments, reducing the time complexity from O(2^n) down to linear O(n).

Example #

fibMemo(6) call trace with cache:
- Computes fib(2), fib(3), fib(4), fib(5), fib(6) once each
- Lookup fib(4) from cache in O(1) instead of branching again
- fibMemo(50) returns 12586269025 instantly!

Input : Target index n and optional cache object
Output : Nth Fibonacci number computed in O(n) time complexity.

Implementation #

// 1. Naive Recursion — O(2^n) Exponential Time (Freezes around n = 42)
function fibonacciSlow(n) {
  if (n <= 2) return 1;
  return fibonacciSlow(n - 1) + fibonacciSlow(n - 2);
}

// 2. Memoized Recursion — O(n) Linear Time
function fibonacciMemo(index, cache) {
  cache = cache || [];

  if (cache[index]) {
    return cache[index];
  } else {
    if (index < 3) {
      return 1;
    } else {
      cache[index] =
        fibonacciMemo(index - 1, cache) + fibonacciMemo(index - 2, cache);
    }
  }

  return cache[index];
}

// 3. Generic Higher-Order Memoize Utility
function memoize(fn) {
  var cache = {};
  return function (arg) {
    if (Object.prototype.hasOwnProperty.call(cache, arg)) {
      return cache[arg];
    }
    var result = fn(arg);
    cache[arg] = result;
    return result;
  };
}

console.log(fibonacciMemo(50)); // 12586269025

Main Point: Memoization trades a small O(n) memory footprint (the cache array or object) to eliminate redundant recursive tree branches and achieve O(n) execution speed.

Credits #

Photo by Shahadat Rahman

← Home