# Untitled

unknown

python

2 years ago

2.1 kB

1

Indexable

Never

^{}

import time def factorial(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 factorial(n - 1) * n def factorial_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 = factorial_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: factorial(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: factorial_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()