Python Fibonacci

In [1]:

def fib(n):
   if n<2:
       return n
   return fib(n-1)+fib(n-2)

In [2]:

%timeit fib(20)

3.72 ms ± 140 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [2]:

%load_ext Cython

In [3]:

%%cython
  
def fib_cython(n):
    if n<2:
        return n
    return fib_cython(n-1)+fib_cython(n-2)

In [4]:

%timeit fib_cython(20)

1.25 ms ± 8.76 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [5]:

from functools import lru_cache as cache
@cache(maxsize=None)
def fib_cache(n):
    if n<2:
        return n
    return fib_cache(n-1)+fib_cache(n-2)

In [6]:

%timeit fib_cache(20)

138 ns ± 0.655 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

In [ ]: