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)