Recursive

code: python

# O(2^n), O(n)

def f(n: int) -> int:

if n == 0:

return 0

if n == 1:

return 1

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

# f(0) -> 0

# f(1) -> 1

# f(2) -> f(1) + f(0) -> 1

# f(3) -> f(2) + f(1) -> 2

# f(4) -> f(3) + f(2) -> 3

# f(5) -> f(4) + f(3) -> 5

def test_f():

assert f(0) == 0

assert f(1) == 1

assert f(2) == 1

assert f(3) == 2

assert f(4) == 3

assert f(5) == 5

assert f(10) == 55