Memoize a recursive Fibonacci

Plain recursive Fibonacci recomputes the same subtrees exponentially often — fib(50) is roughly forty billion calls. Adding a cache in the enclosing scope turns it linear, and it is the clearest demonstration there is of why a closure over mutable state is useful.

Implement createFib(). It returns a function fib(n) where fib(0) is 0, fib(1) is 1, and fib(n) is fib(n - 1) + fib(n - 2). Results are cached in the closure, so the cache survives between separate top-level calls to fib. The returned function also exposes a misses property counting the cache misses: every time fib is called with an n that is not already in the cache, misses rises by one and the computed value is cached — including the base cases 0 and 1. So a freshly created fib called once with 10 ends up with misses of 11, and calling fib(10) again adds nothing. Each call to createFib() produces an independent function with its own empty cache and its own misses of 0.

const fib = createFib();

fib(0);  // 0
fib(1);  // 1
fib(7);  // 13
fib(50); // 12586269025 — instant

const fib = createFib();
fib(10);
fib.misses; // 11 — one per cached value, base cases included

fib(10);
fib.misses; // 11 — cache hit, no new work
fib(12);
fib.misses; // 13 — only 11 and 12 were new