Modify the recursive Fibonacci function to employ the memoization technique discussed in this chapter. The function creates a dictionary and then defines a nested recursive helper function named memoizedFib. You will need to create a dictionary to cache the sum of the fib function. The base case of the fib function is the same as before. However, before making any recursive calls, the helper function looks up the value for the function’s current argument in the dictionary (use the method get, with None as the default value). If the value exists, the function returns it and skips any recursive calls. Otherwise, after the helper function adds the results of its two recursive calls, it saves the sum in the dictionary with the current argument of the function as the key. Note: The program should output in the following format: n fib(n) 2 1 4 3 8 21 16 987 32 2178309 ---------------------------------------------------------------------------------- def fib(n): """Returns the nth Fibonacci number.""" if n < 3: return 1 else: return fib(n - 1) + fib(n - 2) def main(): """Tests the function with some powers of 2.""" problemSize = 2 print("%4s%12s" % ("n", "fib(n)")) for count in range(5): print("%4d%12d" % (problemSize, fib(problemSize))) problemSize *= 2 if name == "main": main()

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Related questions

Question

Modify the recursive Fibonacci function to employ the memoization technique discussed in this chapter. The function creates a dictionary and then defines a nested recursive helper function named memoizedFib.

You will need to create a dictionary to cache the sum of the fib function. The base case of the fib function is the same as before. However, before making any recursive calls, the helper function looks up the value for the function’s current argument in the dictionary (use the method get, with None as the default value). If the value exists, the function returns it and skips any recursive calls.

Otherwise, after the helper function adds the results of its two recursive calls, it saves the sum in the dictionary with the current argument of the function as the key.

Note: The program should output in the following format:

n fib(n)

2 1

4 3

8 21

16 987

32 2178309

----------------------------------------------------------------------------------

def fib(n):

"""Returns the nth Fibonacci number."""

if n < 3:

return 1