Modify the recursive Fibonacci function to employ the memoization technique discussed in this chapter. Please use Python code when doing this. Code is provided below.

1. The function should expect a dictionary as an additional argument. The top-level call of the function receives an empty dictionary.
2. The functions keys and values should be the arguments and values of the recursive calls.
3. Use the counter object discussed in this chapter to count the number of recursive calls.

D1={1: {2: {3: 4, 5: 6}, 3: {4: 5, 6: 7}}, 2: {3: {4: 5}, 4: {6: 7}}}

def iterdict(d):

for k,v in d.items():

if isinstance(v, dict):

iterdict(v)

else:

print (k,":",v)

iterdict(D1)

def fib(n, table):

"""Fibonacci function with a table for memoization."""

if n < 3:

return 1

else:

result1 = table.get(n - 1, n - 2)

if result1 is None:

result1 = fib(n - 1, table)

table[n - 1] = result1

def main():

"""Tests the function with some powers of 2."""

problemSize = 2

print("%4s%12s" % ("n", "fib"))

for count in range(5):

print("%4d%12d" % (problemSize, fib(problemSize, {dict})))

problemSize *= 2

if __name__ == "__main__":

main()