calculates the fibonacci sequence using iteration recursion memoization and a simplified form of binet s formula note 1 the iterative recursive memoization functions are more accurate than the binet s formula function because the binet formula function uses floats note 2 the binet s formula function is much more limited in the size of inputs that it can handle due to the size limitations of python floats see benchmark numbers in main for performance comparisons https en wikipedia orgwikifibonaccinumber for more information times the execution of a function with parameters calculates the first n 1indexed fibonacci numbers using iteration with yield listfibiterativeyield0 0 tuplefibiterativeyield1 0 1 tuplefibiterativeyield5 0 1 1 2 3 5 tuplefibiterativeyield10 0 1 1 2 3 5 8 13 21 34 55 tuplefibiterativeyield1 traceback most recent call last valueerror n is negative calculates the first n 0indexed fibonacci numbers using iteration fibiterative0 0 fibiterative1 0 1 fibiterative5 0 1 1 2 3 5 fibiterative10 0 1 1 2 3 5 8 13 21 34 55 fibiterative1 traceback most recent call last valueerror n is negative calculates the first n 0indexed fibonacci numbers using recursion fibiterative0 0 fibiterative1 0 1 fibiterative5 0 1 1 2 3 5 fibiterative10 0 1 1 2 3 5 8 13 21 34 55 fibiterative1 traceback most recent call last valueerror n is negative calculates the ith 0indexed fibonacci number using recursion fibrecursiveterm0 0 fibrecursiveterm1 1 fibrecursiveterm5 5 fibrecursiveterm10 55 fibrecursiveterm1 traceback most recent call last exception n is negative calculates the first n 0indexed fibonacci numbers using recursion fibiterative0 0 fibiterative1 0 1 fibiterative5 0 1 1 2 3 5 fibiterative10 0 1 1 2 3 5 8 13 21 34 55 fibiterative1 traceback most recent call last valueerror n is negative calculates the ith 0indexed fibonacci number using recursion calculates the first n 0indexed fibonacci numbers using memoization fibmemoization0 0 fibmemoization1 0 1 fibmemoization5 0 1 1 2 3 5 fibmemoization10 0 1 1 2 3 5 8 13 21 34 55 fibiterative1 traceback most recent call last valueerror n is negative cache must be outside recursuive function other it will reset every time it calls itself calculates the first n 0indexed fibonacci numbers using a simplified form of binet s formula https en m wikipedia orgwikifibonaccinumbercomputationbyrounding note 1 this function diverges from fibiterative at around n 71 likely due to compounding floatingpoint arithmetic errors note 2 this function doesn t accept n 1475 because it overflows thereafter due to the size limitations of python floats fibbinet0 0 fibbinet1 0 1 fibbinet5 0 1 1 2 3 5 fibbinet10 0 1 1 2 3 5 8 13 21 34 55 fibbinet1 traceback most recent call last valueerror n is negative fibbinet1475 traceback most recent call last valueerror n is too large time on an m1 macbook pro fastest to slowest times the execution of a function with parameters calculates the first n 1 indexed fibonacci numbers using iteration with yield list fib_iterative_yield 0 0 tuple fib_iterative_yield 1 0 1 tuple fib_iterative_yield 5 0 1 1 2 3 5 tuple fib_iterative_yield 10 0 1 1 2 3 5 8 13 21 34 55 tuple fib_iterative_yield 1 traceback most recent call last valueerror n is negative calculates the first n 0 indexed fibonacci numbers using iteration fib_iterative 0 0 fib_iterative 1 0 1 fib_iterative 5 0 1 1 2 3 5 fib_iterative 10 0 1 1 2 3 5 8 13 21 34 55 fib_iterative 1 traceback most recent call last valueerror n is negative calculates the first n 0 indexed fibonacci numbers using recursion fib_iterative 0 0 fib_iterative 1 0 1 fib_iterative 5 0 1 1 2 3 5 fib_iterative 10 0 1 1 2 3 5 8 13 21 34 55 fib_iterative 1 traceback most recent call last valueerror n is negative calculates the i th 0 indexed fibonacci number using recursion fib_recursive_term 0 0 fib_recursive_term 1 1 fib_recursive_term 5 5 fib_recursive_term 10 55 fib_recursive_term 1 traceback most recent call last exception n is negative calculates the first n 0 indexed fibonacci numbers using recursion fib_iterative 0 0 fib_iterative 1 0 1 fib_iterative 5 0 1 1 2 3 5 fib_iterative 10 0 1 1 2 3 5 8 13 21 34 55 fib_iterative 1 traceback most recent call last valueerror n is negative calculates the i th 0 indexed fibonacci number using recursion calculates the first n 0 indexed fibonacci numbers using memoization fib_memoization 0 0 fib_memoization 1 0 1 fib_memoization 5 0 1 1 2 3 5 fib_memoization 10 0 1 1 2 3 5 8 13 21 34 55 fib_iterative 1 traceback most recent call last valueerror n is negative cache must be outside recursuive function other it will reset every time it calls itself prefilled cache calculates the first n 0 indexed fibonacci numbers using a simplified form of binet s formula https en m wikipedia org wiki fibonacci_number computation_by_rounding note 1 this function diverges from fib_iterative at around n 71 likely due to compounding floating point arithmetic errors note 2 this function doesn t accept n 1475 because it overflows thereafter due to the size limitations of python floats fib_binet 0 0 fib_binet 1 0 1 fib_binet 5 0 1 1 2 3 5 fib_binet 10 0 1 1 2 3 5 8 13 21 34 55 fib_binet 1 traceback most recent call last valueerror n is negative fib_binet 1475 traceback most recent call last valueerror n is too large time on an m1 macbook pro fastest to slowest 0 0012 ms 0 0031 ms 0 0062 ms 0 0100 ms 0 0153 ms 257 0910 ms
import functools
from collections.abc import Iterator
from math import sqrt
from time import time


def time_func(func, *args, **kwargs):
    
    start = time()
    output = func(*args, **kwargs)
    end = time()
    if int(end - start) > 0:
        print(f"{func.__name__} runtime: {(end - start):0.4f} s")
    else:
        print(f"{func.__name__} runtime: {(end - start) * 1000:0.4f} ms")
    return output


def fib_iterative_yield(n: int) -> Iterator[int]:
    
    if n < 0:
        raise ValueError("n is negative")
    a, b = 0, 1
    yield a
    for _ in range(n):
        yield b
        a, b = b, a + b


def fib_iterative(n: int) -> list[int]:
    
    if n < 0:
        raise ValueError("n is negative")
    if n == 0:
        return [0]
    fib = [0, 1]
    for _ in range(n - 1):
        fib.append(fib[-1] + fib[-2])
    return fib


def fib_recursive(n: int) -> list[int]:
    

    def fib_recursive_term(i: int) -> int:
        
        if i < 0:
            raise ValueError("n is negative")
        if i < 2:
            return i
        return fib_recursive_term(i - 1) + fib_recursive_term(i - 2)

    if n < 0:
        raise ValueError("n is negative")
    return [fib_recursive_term(i) for i in range(n + 1)]


def fib_recursive_cached(n: int) -> list[int]:
    

    @functools.cache
    def fib_recursive_term(i: int) -> int:
        
        if i < 0:
            raise ValueError("n is negative")
        if i < 2:
            return i
        return fib_recursive_term(i - 1) + fib_recursive_term(i - 2)

    if n < 0:
        raise ValueError("n is negative")
    return [fib_recursive_term(i) for i in range(n + 1)]


def fib_memoization(n: int) -> list[int]:
    
    if n < 0:
        raise ValueError("n is negative")
    
    
    cache: dict[int, int] = {0: 0, 1: 1, 2: 1}  

    def rec_fn_memoized(num: int) -> int:
        if num in cache:
            return cache[num]

        value = rec_fn_memoized(num - 1) + rec_fn_memoized(num - 2)
        cache[num] = value
        return value

    return [rec_fn_memoized(i) for i in range(n + 1)]


def fib_binet(n: int) -> list[int]:
    
    if n < 0:
        raise ValueError("n is negative")
    if n >= 1475:
        raise ValueError("n is too large")
    sqrt_5 = sqrt(5)
    phi = (1 + sqrt_5) / 2
    return [round(phi**i / sqrt_5) for i in range(n + 1)]


if __name__ == "__main__":
    from doctest import testmod

    testmod()
    
    num = 30
    time_func(fib_iterative_yield, num)  
    time_func(fib_iterative, num)  
    time_func(fib_binet, num)  
    time_func(fib_memoization, num)  
    time_func(fib_recursive_cached, num)  
    time_func(fib_recursive, num)