Make a slow function fast with one line.
What to build
A memoized version of the Fibonacci function.
Requirements
- Add memoization so that
fib(80)finishes immediately. - Keep the function recursive.
Input
One whole number n.
Output
The value of F(n).
Constraints
n is from 0 to 80.
Example
Input:
10
Output:
55
Why it works
Without memoization, the number of calls roughly doubles at each step of n. With it, each value of n is computed once.
Examples
Example 1 · Input
10
Expected output
55
Example 2 · Input
1
Expected output
1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Add @lru_cache(maxsize=None) above the def line.
Hint 2
The import line is already written for you.
Solution
Show one correct solution (try it yourself first)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(int(input())))