Fibonacci

The Fibonacci sequence is 1, 1, 2, 3, 5, 8, .... Each successive number is found by adding the previous two. Create a recursive algorithm to compute the nth number in the Fibonacci sequence. Use memoization to get the last test to pass in a respectable about of time.

fib(1) -> 1
fib(2) -> 1
fib(3) -> 2
fib(4) -> 3
fib(5) -> 5

You can learn more from Free Code Camp’s Dynamic Programming video.

Starter Code

def fib(n: int) -> int:
    pass

Tests

from main import fib


def test_fib():
    assert fib(6) == 8
    assert fib(7) == 13
    assert fib(8) == 21
    assert fib(50) == 12586269025
    assert fib(100) == 354224848179261915075