[Solved] IT 210 Fundamentals of Programming Lab 9

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(1O): 354224848179261915075. fib2 was called 197 times.

fibWithHe1p(500) : 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125. fib2 was called 997 times

Each member of the group must make a submission to D2L with your own name as a comment on line 1 and the name or names of other group members on the next line. If you do the lab solo, I will deduct 20 points. Submit a copy of the lab to the Lab 9 D2L dropbox not later than 11:59 pm Monday evening. Name your file Lab09.py.