# 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()```