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.

What it has to do

• Return correct Fibonacci numbers, with fib(0) of 0 and fib(1) of 1.
• Cache results in the closure so fib(50) returns immediately.
• Keep the cache between separate calls to fib.
• Track misses: one per n that had to be computed, base cases included.
• Give each createFib() its own cache and its own misses counter.

Your workspace