fibonaci.py

def fibonaci_recursive(n):
    if n <= 2:
        return 1

    return fibonaci_recursive(n-1) + fibonaci_recursive(n-2)


def fibonaci_dp_1(n):
    memo = {}
    for i in range(1, n + 1):
        if i <= 2:
            memo[i] = 1
        else:
            memo[i] = memo[i - 1] + memo[i - 2]
    return memo[n]


def fibonaci_dp_2(n):
    memo = [1, 1]
    for i in range(n):
        if i > 1:
            memo[1], memo[0] = memo[1] + memo[0], memo[1]

    return memo[1]


def fibonaci_dp_3(n):
    m1, m2 = 1, 1
    for i in range(2, n):
        m2, m1 = m2 + m1, m2

    return m2


if __name__ == '__main__':
    from timeit import timeit
    n = 10
    for fib in (
        fibonaci_recursive,
        fibonaci_dp_1,
        fibonaci_dp_2,
        fibonaci_dp_3,
    ):
        print(f'fib.__name__({n}) = {fib(n)}')
        print(timeit(f'{fib.__name__}({n})', setup=f'from __main__ import {fib.__name__}'))
        print()
        print()

output:

fib.__name__(10) = 55
18.16180771300003


fib.__name__(10) = 55
2.605323016


fib.__name__(10) = 55
2.074666065000031


fib.__name__(10) = 55
0.9082165670000109