Question

To get some practice with recursion.

You can do all this in one driver program.

Write a recursive method to compute the result of the Fibonacci sequence:

Fibonacci(N) = Fibonacci(N -1) + Fibonacci(N-2)

N == 0 is 0

N == 1 is 1

Testing: Display the result for Fibonacci(N) and the number of function calls for N = 2, 5 and 10.

Answer 1

#Code executed in Python 3

#Enter the input variable
N=int(input('Enter the number:'))
#Function to compute Fibonacci sequence:0,1,1,2,3,5,8,13,21,34,55,89,...
def fib(N):
#Base case Fibonacci(0) = 0
if N==0:
return 0
#Base case Fibonacci(1) = 1
elif N==1:
return 1
#Recursively finding the next value
elif N > 1:
return fib(N-1)+fib(N-2)
#In case N is less than 0
else:
print('Invalid Input')
  
#Printing the result of the sequence
print('Result of Fibonacci sequence:',fib(N))
#General term for computing number of function calls
Number_of_calls=2*fib(N)-1
#Printing the number of function calls
print('Number of function calls:',Number_of_calls)

Code snapshot:-

Output snapshot:-