Memoization stores the result of an expensive function call under a key derived from its input arguments. On a later call with the same inputs, a cache hit returns the stored result instead of running the full function again. It trades space for less repeated computation and is most useful when the same inputs occur often. section 6.9
Recursive Fibonacci calculation makes the repeated work visible: calculating one value repeatedly calculates smaller values. A memoized version keeps an internal cache indexed by n. It returns the base cases directly, calculates each larger value only when its cache entry is empty, and then reuses that value. The cache is created for each outer call, so this implementation removes repetition within a calculation rather than retaining results across separate calls. section 7.7
Listing 7.3 Generating a number in the Fibonacci sequence using recursion with memoization
pub fn fib_memoization(n: u64) -> u64 {
fn fib(n: u64, cache: &mut Vec<u64>) -> u64 {
if n <= 1 {
return n;
}
if cache[n as usize] == 0 {
let result = fib(n - 1, cache) + fib(n - 2, cache);
cache[n as usize] = result;
}
cache[n as usize]
}
let mut cache = vec![0; (n + 1) as usize];
fib(n, &mut cache)
}
The Rust implementation shows the input-indexed cache, the cache check, and the recursive calculation on a miss. section 7.7
Measure the saved work
A Criterion benchmark of fib_recursive(10) reports about 157 ns for plain recursion and 44 ns with memoization—over 3× faster. That does not make caching the fastest option here: an iterative implementation measures about 5 ns. Benchmark the alternatives rather than assuming a cache is always worthwhile. section 7.7
The same idea can apply at a different boundary: caching a REST API response in a client reuses a result that may combine computation and data access. Unlike the per-call Fibonacci cache, such a result may need a freshness limit. A time-to-live set too low reduces cache hits; one set too high risks stale data. Memoization also differs from a materialized view: the former targets repeated computations, while the latter speeds retrieval from a prebuilt organization of data. section 6.11 section 6.9
