I will never ever eat a tomato.py

[esthicodes]

fibonacci.py

"""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 thanthe Binet's formula function because the Binet formula function uses floatsNOTE 2: the Binet's formula function is much more limited in the size of inputsthat it can handle due to the size limitations of Python floatsRESULTS: (n = 20)fib_iterative runtime: 0.0055 msfib_recursive runtime: 6.5627 msfib_memoization runtime: 0.0107 msfib_binet runtime: 0.0174 ms

""" from math import sqrtfrom time import time def time_func(func, *args, **kwargs): """ Times the execution of a function with parameters """ 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(n: int) -> list[int]: """ 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): ... Exception: n is negative """ if n < 0: raise Exception("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]: """ 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): ... Exception: n is negative """ def fib_recursive_term(i: int) -> int: """ Calculates the i-th (0-indexed) Fibonacci number using recursion """ if i < 0: raise Exception("n is negative") if i < 2: return i return fib_recursive_term(i - 1) + fib_recursive_term(i - 2) if n < 0: raise Exception("n is negative") return [fib_recursive_term(i) for i in range(n + 1)] def fib_memoization(n: int) -> list[int]: """ 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)