Memoization & Dynamic Programming

Overview

Memoization is an optimisation that stores the results of expensive function calls and returns the cached result when the same inputs are seen again. It is a specialised form of caching applied at the function level, and it only works correctly on pure functions, those that return the same output for the same input with no side effects.

Origin

The term was coined by Donald Michie in 1968. Dynamic programming, formalised in the 1950s by Richard Bellman, uses memoization as its core mechanism, breaking problems into overlapping subproblems and caching solutions to avoid recomputation.

Examples

// Naive: exponential time O(2^n)
function fib(n) {
  if (n <= 1) return n
  return fib(n - 1) + fib(n - 2)
}

// Memoized: linear time O(n)
function memoize(fn) {
  const cache = new Map()
  return function(...args) {
    const key = JSON.stringify(args)
    if (cache.has(key)) return cache.get(key)
    const result = fn.apply(this, args)
    cache.set(key, result)
    return result
  }
}

const fibMemo = memoize(function fib(n) {
  if (n <= 1) return n
  return fibMemo(n - 1) + fibMemo(n - 2)
})

fibMemo(40)  // instant; naive takes seconds

class ReportService
  def summary
    @summary ||= compute_expensive_summary
  end

  def user_permissions(user_id)
    @permissions ||= {}
    @permissions[user_id] ||= fetch_permissions(user_id)
  end

  private

  def compute_expensive_summary
    # Runs once per instance; result cached in @summary
    db.execute('SELECT ...')
  end
end

Use Cases

• 01Recursive algorithms with overlapping subproblems (Fibonacci, shortest path, edit distance)
• 02Expensive database lookups called repeatedly with the same parameters within a request
• 03Computed properties in UI components that depend on unchanged inputs
• 04Parsing and compilation steps that process the same grammar rules repeatedly
• 05API clients that cache responses for idempotent GET requests

When Not to Use

• //On impure functions, if the function has side effects or reads from mutable state, cached results will be stale
• //When the input space is unbounded and unique, the cache grows without bound and wastes memory
• //When function call overhead is already negligible, memoization adds complexity for no gain
• //In concurrent contexts without locking: two threads may both compute and both try to write the cache simultaneously

Technical Notes

• Choose the cache key carefully. JSON.stringify fails on circular references and does not distinguish objects with the same fields but different identity
• Set a cache size limit (LRU eviction) when the input cardinality is high but bounded
• React's useMemo and useCallback are specialised memoization for component renders, they cache based on a dependency array, not function arguments
• In distributed systems, memoization at the process level means different nodes maintain separate caches, consistency is not guaranteed without a shared cache layer (Redis)