Cache a Slow Fibonacci with lru_cache
Write a recursive Fibonacci function, apply @lru_cache to a second version, and confirm both agree on the answer and that a cached lookup is faster than the uncached computation.
Approach: define fibuncached (plain recursion) and fibcached (decorated with @lrucache), compute fib(n) with both, warm the cache, then time a fresh call to fibcached against the original uncached call.
Input: One line: an integer n.
Output: Three lines: "fib(<n>) = <value>", "Results match: True", and "Cache lookup faster than fresh computation: True".
28
fib(28) = 317811 Results match: True Cache lookup faster than fresh computation: True
- 10 <= n <= 30
Hint 1
@lru_cache(maxsize=None) goes directly above the cached recursive function's def line.
Hint 2
Call fib_cached(n) once first to "warm" the cache before timing the second, cached call.
Hint 3
Compare the warmed cached-call time against the uncached call's time — the cached lookup should be dramatically faster.
fibuncached recomputes every sub-call from scratch, taking exponential time. fibcached is decorated with @lru_cache, so calling it once populates the cache for every (n) it touches; a second call for the same n becomes an instant dictionary lookup. Warming the cache before timing it, then comparing that cached-call time against the uncached call's time, demonstrates the speedup reliably and by a large margin, without needing to print (non-reproducible) raw timing numbers.