In [1]: %run fib.py

In [2]: %time fib(40)
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 85.4 µs
Out[2]: 165580141

In [3]:
Do you really want to exit ([y]/n)? y
carpodolyaka@rpodolyaka-pc:~/sandbox$ cat fib.py
import functools


@functools.lru_cache()
def fib(n):
    if n < 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)


def fib_tail(n, a=1, b=1):
    if n < 2:
        return a
    else:
        return fib_tail(n - 1, a + b, a)