Question

Exponential Fibonacci - Using naive recursive method. Report the largest fibonacci number you are able to compute without your program taking more than 30 seconds..

Complete in python and show screenshots of output and explain your steps

Answer 1

NOTE: I have tried so many times in IDLE shell and 241578107 is the largest fibonacci number I got. You can try 38 or 39 in Fibonacci function if you have doubt.

CODE:

#use timeit module to calculate the execution time
import timeit
s_time = timeit.default_timer()
# Function for nth Fibonacci number
def Fibonacci(n):
if n<0:
print("Incorrect input")
# First Fibonacci number is 0
elif n==0:
return 0
# Second Fibonacci number is 1
elif n==1:
return 1
# Recursive method for Fibonacci
else:
return Fibonacci(n-1)+Fibonacci(n-2)
print(Fibonacci(37))
#calculate the end time
e_time = timeit.default_timer()
print("%s sec"%(e_time-s_time))

# Give me a like