def fib_recursion(n):
    if 0 <= n <= 1:
        return n

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


print(fib_recursion(8))


def fib_dp(n):
    res = [0, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        res[i] = res[i - 1] + res[i - 2]

    return res[n]


print(fib_dp(8))