Python program to compute the nth Fibonacci number using recursive function…

Question:

In python….Modify the recursive Fibonacci program given in the textbook so that it prints tracing information. Specifically, have the function print a message when it is called and when it returns.

For example, the output should contain lines like these:
Computing fib(4) OR

Leaving fib(4) returning 3

Answer:

“””
Python version : 3.6
Python program to compute the nth fibonacci number using recursive function
where fibonacci sequence is 0, 1, 1, 2, 3, 5,…
“””
def fib(n):
   # display the value of n for which the function has been called
   print(‘Computing fib(%d)’%(n))
   if n <= 2: # base case: the first 2 fibonacci numbers are 0 and 1
       result = n-1
       print(‘Leaving fib(%d) returning %d’%(n, result))
       return result
   else:
       # the fibonacci numbers where n > 2, are sum of the previous 2 fibonacci numbers in sequence
       # call the function for n-1 and for n-2 and then add the numbers returned by the functions
       result = fib(n-1)+fib(n-2)
       print(‘Leaving fib(%d) returning %d’%(n, result))
       return result

# test the function      
print(‘5th fibonacci number:’,fib(5))
#end of program

Code Screenshot:

Output:

Leave a Comment

Your email address will not be published. Required fields are marked *