24.2.4. Memoization Technique

Try these first

1. 1.

   What is memoization?

   Hint

   Think about how it relates to reducing repetitive work.

2. 2.

   What is the base case in recursion?

   Hint

   It's the stopping point for recursion.

3. 3.

   What term refers to storing previously computed results in a recursive function?

   • Recursion
   • Memoization
   • Dynamic Programming

   Hint

   Think about the technique that helps speed up function calls.

4. 4.

   True or False: Memoization can improve the time complexity of certain recursive algorithms.

   • True
   • False

   Hint

   Consider the effect on redundant calculations.

5. 5.

   Implement a function using memoization to calculate the nth Fibonacci number in Python.

   Hint

   Think about how to store each result in a dictionary or a similar structure.

6. 6.

   Given the overlapping subproblems property, compare memoization performance with simple recursion in terms of function calls for Fibonacci(6). Show how many calls are made without and with memoization.

   Hint

   Calculate recursive calls manually or trace them out in a tree diagram.