Fibonacci Using Recursion and Memoization
Memoization stores previously calculated results so recursive calls do not repeat the same work.
What is Fibonacci Using Recursion and Memoization?
Memoization stores previously calculated results so recursive calls do not repeat the same work.
Generate a Fibonacci value with recursive Python and memoization.
When should you use it?
- Practice problem solving and data structures.
- Process data when every algorithm step must be explicit.
- Prepare for programming exercises, exams, and interviews.
Example code
main.py
from functools import cache
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
print(fibonacci(10))Expected output
55How it works
The cache decorator remembers results by argument. This reduces the exponential naive recursion to O(n) time.
Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.
Practice exercises
Modify the runnable example with the exercises below to build understanding beyond copying the result.
- Try empty, single-item, and duplicate-value inputs.
- Print state after every step to observe the algorithm.
- Benchmark 100, 1,000, and 10,000 items, then compare another approach.