**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:**