Memoization

Memoization stores the result of a function for an input and reuses it when the same input appears again. It is most reliable when the function is referentially transparent: equal inputs imply an equal result and evaluation has no required side effects.

From exponential recursion to linear work

Naive Fibonacci recursion recomputes the same subproblems. The memoized version evaluates each non-negative argument at most once:

static BigInteger fibonacci(int n, Map<Integer, BigInteger> memo) {
    if (n < 0) throw new IllegalArgumentException("n must be non-negative");
    BigInteger known = memo.get(n);
    if (known != null) return known;

    BigInteger result = n < 2
            ? BigInteger.valueOf(n)
            : fibonacci(n - 1, memo).add(fibonacci(n - 2, memo));
    memo.put(n, result);
    return result;
}

Assuming expected constant-time map access, there are n + 1 states, constant non-recursive work per state, Θ(n) stored results, and Θ(n) call-stack depth. Tabulation can retain the same time bound while reducing auxiliary space for this recurrence to Θ(1).

The key is part of correctness

The key must contain every input that can affect the result, including relevant configuration, locale, permissions, or algorithm mode. Mutable keys are unsafe when their equality or hash code changes after insertion. Floating-point inputs and very large object graphs also require an explicit equivalence policy.

Do not memoize an operation merely because its method signature looks like a function. Time, random values, database state, environment variables, and external calls are hidden inputs unless captured explicitly.

Lifetime, bounds, and concurrency

A per-invocation table has a natural lifetime and is often enough for dynamic programming. A process-wide table needs an eviction or reachability policy; otherwise memoization becomes a memory leak. Under concurrency, a thread-safe map protects its structure but does not necessarily prevent duplicate computation. Single-flight coordination may be useful only when duplicate work is expensive and failure cleanup is well defined.

Memoizing failures can suppress recovery. Decide whether an exception, empty result, or timeout is reusable and for how long.

Memoization is not general caching

Memoization preserves a function's result for equal inputs. An application cache usually mirrors data whose source can change and therefore needs freshness, invalidation, capacity, and outage semantics. The implementations may both use maps, but their correctness contracts differ.

Verification checklist

• compare results with a non-memoized oracle on small inputs;
• count state evaluations to confirm reuse;
• test empty, base, maximum, and invalid inputs;
• test key equality and mutation assumptions;
• measure retained memory as well as elapsed time.