Memoization

Example

function memoize(callable $fn): Closure {
  $cache = [];
  return function() use ($fn, &$cache) {
    $key = serialize(func_get_args());
    if (!isset($cache[$key])) {
      $cache[$key] = $fn(...func_get_args());
    }
    return $cache[$key];
  };
}

$fib = memoize(function(int $n) use (&$fib): int {
  return $n <= 1 ? $n : $fib($n-1) + $fib($n-2);
});

$fib(40); // O(n) instead of O(2^n)

When to apply

• Pure function (same input → same output, always)
• Expensive computations called repeatedly with the same arguments
• Recursive algorithms with overlapping subproblems (dynamic programming)