[Python] Modify the recursive Fibonacci program given in the chapter 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) Leaving fib(4) returning 3. Use your modified version of fib to compute fib(10) and count how many times fib(3) is computed in the process.
# fib.py
def loopFib(n):
# pre: n > 0
# returns the nth Fibonacci number
curr = 1
prev = 1
for i in range(n-2):
curr, prev = curr + prev, curr
return curr
def recFib(n):
if n < 3:
return 1
else:
return recFib(n-1) + recFib(n-2)