Untitled

import time

def foo(n):
  '''
  input: int 
  return: int
  Calculates the factorial of a given number using a recursive algorithm
  ''' 
  # Base case
  if n <= 1:
    return 1
    
  # Recursive case
  return foo(n - 1) * n

def foo_memoized(n, cache = {}):
  '''
  input: int 
  return: int
  Calculates the factorial of a given number using a recursive algorithm with memoization.
  ''' 

  if n in cache:
    return cache[n]

  # Base case
  elif n <= 1:
    return 1

  # Recursive case: calculate the factorial of n and store the result in the dictionary
  result =  foo_memoized(n - 1) * n
  cache[n] = result 

  return result 


def main():
  '''
  Compares the runtime performance of the recursive factorial algorithm and the recursive factorial algorithm with memoization.
  '''

  # Set the total number of random numbers to generate 
  total_nums = 400

  # Create a list of random integers in the range of 0, 400
  nums = [random.randint(1, total_nums) for _ in range(total_nums + 1)]
  print(f"Creating a list of {total_nums} random integers in the range of [0, 400]")

  # Calculate the factorial of each number in the list using the recursive algorithm
  start = time.perf_counter()
  for num in nums:
    foo(num)
  end = time.perf_counter()
  recursive_time = end - start

  print(f"\nRunning the factorial recursive algorithm using {total_nums} random integers from the list")
  print(f"\nTime taken by recursive algorithm function:{recursive_time}")

  # Calculate the factorial of each number in the list using the recursive algorithm with memoization
  start = time.perf_counter()
  for num in nums:
    foo_memoized(num, cache = {})
  end = time.perf_counter()
  memoized_time = end - start

  print(f"\nTime taken by recursive algorithm with memoization function: {memoized_time}")

  if recursive_time < memoized_time:
    print("\nRecursive algorithm time has a better runtime.")
  else:
      print("\nRecursive algorithm time with memoization has a better runtime.")

if __name__ == "__main__":
  main()