Fibonacci

# Functions to calculate nth Fibonacci number
# Memoized and Tabulated versions
from functools import lru_cache
from random import choice
from time import time

# top down/memoized version
def td_fib(n, lookup):
    # base case
    if n == 0 or n == 1:
        lookup[n] = n

    # if the value was not calculated previously then calculate it
    if lookup[n] is None:
        lookup[n] = td_fib(n-1, lookup) + td_fib(n-2, lookup)

    # return the value corresponding to that value of n
    return lookup[n]


# tabulated/bottom up version
def tab_fib(n):
    # array declation
    f = [0] * (n+1)

    # base case assignment
    f[1] = 1

    # calculating the fibonacci and storing the values
    for i in range(2, n+1):
        f[i] = f[i-1] + f[i-2]
    return f[n]


# lru_cache/memoized version
@lru_cache(maxsize=None)
def mem_fib(n):
    if n < 2: return n
    return mem_fib(n - 1) + mem_fib(n - 2)


def main():
    # n = choice(range(101))
    n = 100
    start = time()
    # declaration of lookup table
    # handles till n = 100
    lookup = [None] * 101
    print(f'Memoized {n} is {td_fib(n, lookup)}')
    print(f'{time() - start} seconds')
    # print([i for i in lookup if i != None])

    print('')
    start = time()
    print(f'Tabulated {n} is {tab_fib(n)}')
    print(f'{time() - start} seconds')

    print('')
    start = time()
    print(f'LRU Cache {n} is {mem_fib(n)}')
    print(f'{time() - start} seconds')


if __name__ == '__main__':
    main()