import time

# store recent function calls into a dictionary
cache_values = {}
def fibonacci(n):
    #   check if the given number is less than 0
 if n < 0:
        # output an error message stating that the number given is incorrect
  raise ValueError("Has to be a positive integer!")
 # check if the value is in our dictionary
 if n in cache_values:
  # return that value if it is
  return cache_values[n]

# if that fails you will need to compute the value
 if n == 0:
  value = 0
# check if the value is equal to 1 or 2
 elif n == 1 or n == 2:
  # store the value 1 into a variable to later store it in our dictionary
  value = 1
  # otherwise if the value is greater than 2
 elif n > 2:
  # get the sum of the previous 2 terms and store it into our value variable
  value = (fibonacci(n - 1) + fibonacci(n - 2))

# return and store the value into our dictionary above
 cache_values[n] = value
 return value

if __name__ == "__main__":
    start = time.time()
    print("\nInitializing fibonacci please wait...")
    print(fibonacci(100))
    load_time = round(time.time() - start, 4)
    print("\nThis took: {}.".format(load_time))