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 <>
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()