memoization_example.py

#! /usr/bin/python3
# ==================================================================
# Recursion, the Fibonacci Sequence and Memoization
# From: https://www.youtube.com/watch?v=Qk0zUZW-U_M
# ------------------------------------------------------------------
# Wikipedia - Memoization
# In computing, memoization or memoisation is an optimization
# technique used primarily to speed up computer programs by storing
# the results of expensive function calls and returning the cached
# result when the same inputs occur again.
# ==================================================================

from functools import lru_cache

@lru_cache(maxsize = 1000)
def fibonacci(n):
    # check that the input is a positive integer
    if type(n) != int:
        raise TypeError("n must be a positive int")
    if n < 1:
        raise ValueError("n must be a positive int")

    # compute the Nth term
    if n == 1:
        return 1
    if n == 2:
        return 1
    elif n > 2:
       return fibonacci(n-1) + fibonacci(n-2)

# display the first 50 fibonacci numbers
for n in range(1,51):
    print(fibonacci(n))

# display the ratio between consecutive terms
# (it turns out it is the golden ratio) 
for n in range(1,51):
    print(fibonacci(n+1) / fibonacci(n))