xsnippet logotype

xsnippet

#362506, Untitled [ Text only ]

by Guest
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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)