# a program that traces the fib function
#

def loop_fib(n):
    curr = 1
    prev = 1
    for i in range(n-2):
        curr, prev = curr+prev, curr
    return curr

def rec_fib(n):
    print "Computing fib(%d)"%n
    if n<3:
        return_value = 1
    else:
        return_value = rec_fib(n-1) + rec_fib(n-2)

    print "Leaving fib(%d) returning %d"%(n,return_value)
    return return_value

def main():
 
    n = input("Computing the n-th Fibonacci number. Enter n. ")
    print "Fib(%d) is %d"%(n,loop_fib(n))

    print
    print "Trace the recusive computation of Fibonacci numbers"
    print
    f = rec_fib(n)
    print
    print "Fib(%d) is %d"%(n,f)
    print

main()