import time
def fib(n) :
    if n==0 :
        return 0
    elif n==1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

def fib2(n):
    f = (n+1) * [0]
    f[0] = 0
    if(n>0):
        f[1] = 1
        for i in range(2,n+1):
            f[i] = f[i-1] + f[i-2]
    return f[n]



for i in range(30,36):
    stime = time.time()
    fib(i)
    print('%2d %10.5f' % (i, time.time()-stime))


for i in range(30,36):
    stime = time.time()
    fib2(i)
    print('%2d %10.5f' % (i, time.time()-stime))