def fibonacciR(n):
    global counter
    counter +=1
    if n<2: return 1
    return fibonacciR(n-1)+fibonacciR(n-2)


def fibonacciI(n):
    global counter
    fib = fibM1 = fibM2 = 1
    for i in range(2,n+1):
        fibM2 = fibM1
        fibM1 = fib
        fib = fibM1 + fibM2
        counter +=3
    return fib

#for i in range(10):
#    print(fibonacci(i))

counter = 0
print(fibonacciR(30), counter)
counter = 0
print(fibonacciI(30), counter)