This program requires you to work in a group of two or three to write Python code that implements a fast recursive
Fibonacci with a helper function. The start code is on D2L and shown here.
# Your name
# Your team member name(s)
# Fibonacci Lab
# This is the standard recursive implementation of the fibonacci calculation def fibl(n):
global count # These fi rst two statements are only used to count the # number of recursive calls.
return I else:
return fib1Cn-1) + fib1Cn-2)
# Build the starting dictionary and then call the function that will recurse def fibWithHeIpCn): fibDict = return fibZCn, fibDict)
# This version of fib will check to see if n is in the dictionary and if so,
# simply return the value stored there. If it is not in the dictionary, # perform the calculation, update the dictionary and return the calculated
def fib2Cn, fibDict):
global count # These fi rst two statements are only used to count the count # number of recursive calls.
# Finish writing the code for this implementation. Ensure that you
# use fib2 when recursing, not fibl
if _name " —mat n for x in count
%d. fibl was called %d times.' % (x, fibl(x), count)) pri nt() for x in (3,1Ø,25,3Ø,35,IØØ,5ØØ): # Much larger problems are possible here count = 0
%d. fib? was called %d times. " % (x, fibWithHelp(x), count))
The output of your program should look like this:
fib1(3) : 2. fibl was called 3 times. fib1(10) : 55. fibl was called 109 times.
fib1(25) : 75025. fibl was called 150049 times. fib1(30) : 832040. fibl was called 1664079 times. fibI(35) : 9227465. fibl was called 18454929 times.
fibWithHelp(3) : 2. fib2 was catted 3 times. fibWithHelp(10) : 55. fib2 was called 17 times. fibWithHe1p(25) : 75025. fib2 was called 47 times. fibWithHelp(30) : 832040. fib2 was catted 57 times. fibWithHe1p(35) : 9227465. fib2 was called 67 times.
fibWithHe1p(1ØO): 354224848179261915075. fib2 was called 197 times.
fibWithHe1p(500) : 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125. fib2 was called 997 times
