f1,f2 = fib2(n-1) return (f1+f2,f1) 2. (25 points) We have noted that the number

Question

f1,f2 = fib2(n-1) return (f1+f2,f1)

2. (25 points) We have noted that the number of recursive calls made using the fully-recursive Fibonacci function is Fib(N) 2-1. Implement the efficient Fibonacci function from p.81 of the notes, but add statements that increment a global counter every time the function is called. Your program should then print the final computed value and the count of calls. a. Print results for n 10, 20, 30, 40, 50 b. hat is the relationship between the number of calls and the final computed value? c. Give an explanation for your answer in (b) Submit your program source code and the output requested

Explanation / Answer

def fib(n):
if n<=1:
return n
else:
return(fib(n-1) + fib(n-2))
print(fib(10))
print(fib(20))
print(fib(30))
print(fib(40))
print(fib(50))

2) relation is final vale*2-1 = number of calls

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.