Fibonacci with Memoization

Compute fib(n) recursively. Cache each fib(k) in a memo map so each subproblem is solved at most once.

Algorithm

Canonical input n = 6 produces fib(6) = 8. Replay highlights every memo write and every cache hit.

Basic Implementation

basic.rs

use std::collections::HashMap;

fn fib(n: i32, memo: &mut HashMap<i32, i32>) -> i32 {
	if let Some(&v) = memo.get(&n) {
		return v;
	}
	if n < 2 {
		memo.insert(n, n);
		return n;
	}
	let value = fib(n - 1, memo) + fib(n - 2, memo);
	memo.insert(n, value);
	value
}

fn main() {
	let mut memo: HashMap<i32, i32> = HashMap::new();
	let result = fib(6, &mut memo);
	println!("{}", result);
}

Complexity

Time: O(n) with memoization (vs. O(2^n) without)
Space: O(n) memo + O(n) call stack

Implementation notes

Rust: the recursion takes the memo as &mut HashMap<i32, i32> rather than a global, which keeps Rust's ownership model honest without hiding the lesson behind thread_local! or a Mutex. The if let Some(&v) = memo.get(&n) pattern is the canonical "did I see this key" test.
The replay shows the call stack on one side and the memo map on the other so memo writes and cache hits are visually distinct.

memoization A `HashMap<i32, i32>` keyed by `n` stores each completed subproblem. Before recursing, check `memo.get(&n)`: a hit returns immediately, a miss descends.

explicit memo state The memo is threaded through the recursion as `&mut HashMap<i32, i32>` so the lesson stays about caching, not global state.