24.2.6. Memoized Fibonacci Implementation

Try these first

1. 1.

   What are the first two Fibonacci numbers?

   Hint

   Think about the starting point of the sequence.

2. 2.

   Define memoization in your own words.

   Hint

   Consider its purpose in recursive algorithms.

3. 3.

   What is the time complexity of the naive recursive Fibonacci function?

   • O(n)
   • O(2^n)
   • O(log n)

   Hint

   Think about how many times Fibonacci is called for larger numbers.

4. 4.

   True or False: Memoization avoids redundant calculations.

   • True
   • False

   Hint

   Reflect on what memoization achieves in recursive functions.

5. 5.

   Write an optimized Fibonacci function using memoization in Python. Then compare its execution time with the naive method on increasingly larger inputs.

   Hint

   Focus on how storing values reduces total computation time.

6. 6.

   Design a function that combines memoization with another recursive algorithm of your choice. Analyze the efficiency gains.

   Hint

   Consider well-known algorithms like calculating factorials.