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 1

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