← All Exercises
Memoized Fibonacci
intermediatepython
Background
Memoization transforms exponential recursive Fibonacci into linear time by caching computed results.
Problem
Write a Fibonacci function using functools.lru_cache decorator for automatic memoization, and compare with naive recursion.
Input
A non-negative integer n.
Output
The nth Fibonacci number.
Sample tests
Sample 1
Input: 10
Expected: 55
Your solution
Learning objective
Learn automatic memoization with lru_cache and its impact on recursive algorithm performance.