# 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

“””
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: