It is pretty easy to compute the Nth Fibonacci number using a recursive function. In fact,...

  

Transcribed Image Text:

It is pretty easy to compute the Nth Fibonacci number using a recursive function. In fact, mathematicians express the formula to do that recursively: Better (O F(n) = 1 , n = 0 , n = 1 (F(n-1) + F(n-2), n >1 this is a recurrence relation that says, for the function: if n = 0 return 0 if n = 1 return 1 else return fib(n-1) + fib(n-2) this looks like great pseudocode for a recursive implementation in python. Implement it as a function in your fib.py program. (You can call that function anything you want - but use that name when you recurse.) Remember to use a == to check for equivalence. A single = is for assignment in python! Trace it to check it by drawing activation records for each function call and deleting them on each function return, just as you saw in class. Test it by calling the function with the variable n you had read in with your earlier code, and printing that result. For example, when n is 4, your program should print 3; when 5 it should print 5. Once your program is working, you should right-size your error checking procedure. If you followed the lab exactly, it won't let you enter a value greater than 5, although your function will surely compute a higher fibonacci number. Experiment with your program to identify the highest number your code can compute without exceeding the maximum recursion depth. (HINT: you'll find that for a large number, your program runs so slowly it doesn't seem like it is doing anything. If you get tired of waiting, you can hit Ctrl-C to stop program execution.) Add a print statement in your recursive function like print ("Computing fibonacci ("+str (n)+") ") at the beginning of your recursive function to output what it is doing as it runs. The problem is that it is doing too much recursion - as written, this function recomputes every smaller number in the sequence every time it computes a new number. Don't change your first recursive function, but instead add a better one. Use the same name as before prefix the function name with fast - if your function was called fibonacci before, call this new function fastfibonacci. Implement it using this code: def fastfibonacci (n, memo-()): if n in memo: return memo [n] if n <= 2: else: memo [n] = fastfibonacci (n - 1, memo) + fastfi return memo [n] return 1 There are a couple of new things happening in this code. First. memo is an optional parameter: Here b is predefined and hence is optional. def func (a, b=1098): return a+b 0 Python3 print (func (2, 2)) #this 1 is represented as 'a' in the function and # function uses the default value of b print(func (1)) To learn more about optional parameters, follow this link. Because the parameter is optional you can omit it and call your new function with only It is pretty easy to compute the Nth Fibonacci number using a recursive function. In fact, mathematicians express the formula to do that recursively: Better (O F(n) = 1 , n = 0 , n = 1 (F(n-1) + F(n-2), n >1 this is a recurrence relation that says, for the function: if n = 0 return 0 if n = 1 return 1 else return fib(n-1) + fib(n-2) this looks like great pseudocode for a recursive implementation in python. Implement it as a function in your fib.py program. (You can call that function anything you want - but use that name when you recurse.) Remember to use a == to check for equivalence. A single = is for assignment in python! Trace it to check it by drawing activation records for each function call and deleting them on each function return, just as you saw in class. Test it by calling the function with the variable n you had read in with your earlier code, and printing that result. For example, when n is 4, your program should print 3; when 5 it should print 5. Once your program is working, you should right-size your error checking procedure. If you followed the lab exactly, it won't let you enter a value greater than 5, although your function will surely compute a higher fibonacci number. Experiment with your program to identify the highest number your code can compute without exceeding the maximum recursion depth. (HINT: you'll find that for a large number, your program runs so slowly it doesn't seem like it is doing anything. If you get tired of waiting, you can hit Ctrl-C to stop program execution.) Add a print statement in your recursive function like print ("Computing fibonacci ("+str (n)+") ") at the beginning of your recursive function to output what it is doing as it runs. The problem is that it is doing too much recursion - as written, this function recomputes every smaller number in the sequence every time it computes a new number. Don't change your first recursive function, but instead add a better one. Use the same name as before prefix the function name with fast - if your function was called fibonacci before, call this new function fastfibonacci. Implement it using this code: def fastfibonacci (n, memo-()): if n in memo: return memo [n] if n <= 2: else: memo [n] = fastfibonacci (n - 1, memo) + fastfi return memo [n] return 1 There are a couple of new things happening in this code. First. memo is an optional parameter: Here b is predefined and hence is optional. def func (a, b=1098): return a+b 0 Python3 print (func (2, 2)) #this 1 is represented as 'a' in the function and # function uses the default value of b print(func (1)) To learn more about optional parameters, follow this link. Because the parameter is optional you can omit it and call your new function with only

Answer rating: 100% (QA)

Answer def fibn if n 0 return 0 elif n 1 return 1 else return fib... View the full answer