Memoisation: Definition & Examples

Memoisation stores a completed function result under a key describing its inputs, then reuses that result when the same calculation is requested again. It trades memory for avoided work. For a quant, that can mean valuing a recombining tree node once instead of recalculating it along every path that reaches it.

The important word is same. A node reached at the same time and price is reusable only if those variables describe everything the valuation needs. A path-dependent payoff may also require a running maximum, barrier status or another state variable. Caching by an incomplete state can make the wrong calculation run faster.

Repeated calls versus distinct states

Fibonacci numbers make the repeated work visible without a pricing model. Use the convention

F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}\quad(n\ge2).

Plain recursion evaluates both children every time, stopping at either base case. To obtain

F_{10}=55

, that implementation enters its function body 177 times. The answer does not require 177 different subproblems: only the states

0,1,\ldots,10

occur.

The count includes the initial call and every base-case call. It follows from $C_0=C_1=1$ and $C_n=1+C_{n-1}+C_{n-2}$ , giving $C_{10}=177$ . This count belongs to this two-child implementation and stopping rule; it is not a universal cost of computing Fibonacci numbers.

For Fibonacci 10 with F0=0 and F1=1, plain recursion evaluates states 0 through 10 respectively 34, 55, 34, 21, 13, 8, 5, 3, 2, 1 and 1 times, totalling 177. A cold unbounded cache evaluates each state once, totalling 11 body evaluations.

Same recurrence, different repeated work. Counts are function-body evaluations in a single-threaded run from an empty cache; cache lookups are not counted as body evaluations.

A cache around the recurrence

Python's functools.cache, available since Python 3.9, provides an unbounded argument-to-result cache. This example assumes a nonnegative integer input. It was executed with Python 3.14.4.

from functools import cache

@cache
def fib(n: int) -> int:
    """Return Fibonacci n for a nonnegative integer n."""
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

fib.cache_clear()
print(fib(10))
# 55
info = fib.cache_info()
print(info.hits, info.misses, info.currsize)
# 8 11 11
print(fib(10))
# 55
info = fib.cache_info()
print(info.hits, info.misses, info.currsize)
# 9 11 11

A miss executes the body and saves its result. A hit reuses an existing result. The first request makes 11 misses and 8 hits: 19 calls to the cache wrapper, but only 11 body evaluations. The second top-level request adds one hit and no new body evaluations.

Python evaluates the left child before the right child. On a cold call to fib(10), the descent first reaches state 1, then state 0; completed answers are stored in the order

1,0,2,3,\ldots,10

. Later requests for an already completed state reuse its answer. Caching does not mean that all answers are available before the first descent.

This is a top-down form of dynamic programming: solve needed subproblems recursively and retain the results. Bottom-up iteration can instead fill the same recurrence in dependency order.

Correct keys and a lifetime for the answer

A useful caching design has two obligations: the key identifies the complete calculation, and the saved answer remains valid for as long as it can be reused.

For a pricer, this may require the contract, model parameters, valuation date and an immutable market-data snapshot identifier. An identifier is useful only if it resolves to the same snapshot throughout the cache's lifetime. Reading a changing global curve behind an unchanged key breaks that promise. A refresh should select a new versioned key or invalidate the old results.

Python's cache arguments must be hashable. Lists and dictionaries are not; a tuple works only when all its elements are hashable. Hashability alone does not establish that an object's internal state is fixed or that it captures the complete economic input. Avoid substituting a rounded price for the actual input unless the approximation is deliberate and its error is acceptable.

Call syntax also matters: keyword arguments supplied in a different order may occupy separate entries. Use a consistent calling convention.

Cache results of repeatable calculations whose effects need not run again. A random draw or an order submission is a poor candidate. A cached mutable return value can be changed by its caller and then reused in that changed state. Prefer immutable results or an explicit copying policy. The cache retains arguments and results; cache_clear() invalidates its entries. A bounded lru_cache can limit entry count, while eviction may cause recomputation. Thread-safe cache bookkeeping does not prevent concurrent misses from executing the same calculation more than once.

What the improvement does—and does not—measure

For this Fibonacci recurrence, memoisation reduces an exponential number of body evaluations to a linear number of states. Under a unit-cost arithmetic model with expected constant-time cache operations, the cold calculation takes $O(n)$ work and stores $O(n)$ entries. These are operation and entry counts, not a measured speedup or a byte budget.

Python integers grow as Fibonacci numbers grow. Adding increasingly long integers costs more than adding fixed-size numbers; with ordinary linear-cost integer addition, the sequence of additions takes $O(n^2)$ bit operations and the retained Fibonacci values occupy $O(n^2)$ bits. Keys and Python object overhead add further memory costs.

The first recursive descent still has

O(n)

depth. Memoisation does not remove Python's recursion limit. A bottom-up Fibonacci loop avoids that descent and can retain only the two preceding values, although those integers still grow in bit length. For a more involved recurrence, the required memory depends on which earlier states remain needed.

Dynamic Programming: The SRBOT Recipe develops this choice through overlapping subproblems, dependency order and rod cutting. The public page is a preview; the full lesson requires membership.

A stale-price check

A fictional position has 3 units. A cached valuation keyed only by (symbol, quantity) used a price of USD 125. The latest price becomes USD 130, but the key stays unchanged. What value can the cache return, and what should a valuation using the new price return?

Answer. The cache can return the old USD

3\times125=375

. A fresh valuation is USD

3\times130=390

. Include a stable market-snapshot version in the key and use the new version, or invalidate the old cache before recomputing. Changing the price source does not automatically change an argument-based key.

Sources

Python 3.14: functools.cache and lru_cache: cache scope, argument requirements, statistics, invalidation, retained references and concurrency caveats.
Python 3.14 language reference: evaluation order: left-to-right evaluation.
Python 3.14 glossary: hashable: stable hashes and container eligibility.
Python 3.14: interpreter recursion limit: caching does not remove interpreter stack limits.

Repeated calls versus distinct states

A cache around the recurrence

Correct keys and a lifetime for the answer

What the improvement does—and does not—measure

A stale-price check

Sources

Related terms

Dynamic programming

Iteration

Recursion