This lesson's interactive features are locked, please to keep using them

Fast Fibonacci – Review

You've almost certainly noticed that the memoized and tabulated versions of the Fibonacci algorithm are both faster than the naïve recursive version.

Tabulated Fibonacci

def fibonacci(n: int) -> int:
    fib_arr: list[int] = [0] * (n + 1)
    fib_arr[0] = 0
    if n > 0:
        fib_arr[1] = 1

    for i in range(2, n + 1):
        fib_arr[i] = fib_arr[i - 1] + fib_arr[i - 2]

    return fib_arr[n]

Naïve Fibonacci

def fibonacci(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)