How can I make my recursion program to output factorial of a number more efficient?-CodePudding

I have made a program which outputs the factorial of a number by calling the function: factorial() which uses recursion to calculate and return the value. I have also included a loop to break the program when the User inputs the word "off". Please suggest any improvements

Here is the code:

def factorial(base):
    if base == 0 or base == 1:      
        return 1                                  
    else:
        return base * factorial(base - 1)                            


while True:
   base: int = int(input("Enter a base number: "))
   Result = factorial(base)
   print(f"The factorial of {base} is: {Result}")
   offf: str = input("Enter 'off' to terminate calculations: ")
   if offf == "off":
    print("Calculations Terminated")
    break

Here is the terminal:

CodePudding user response：

While recursive approach seems like a natural thing to do, sadly that is not very efficient, as each call requires a separate stack frame to be created. It also causes problems due to Python's recursion depth limit, which means you this program will raise an exception for any base > 1000. Iterative approach (with loops) is around 2-3 times faster and avoids the recursion limit problems.

def factorial_iterative(base, acc = 1):
    acc = 1
    for i in range(1, base 1):
        acc *= i
    return acc

EDIT: Of course, this still does not beat built-in Python's math.factorial method, which gives us something close to 10x speed up.

Here are the results for base = 995 and 20000 calls to the funtion:

recursive: 12.80487060546875 sec
iterative: 6.284244060516357 sec
math.factorial: 1.1593496799468994 sec

CodePudding user response：

You can try this thing also that will memorise the factorials

res_store = [1]
def factorial(num):
    try:
        return num * res_store[num-1]
    except IndexError:
        for i in range(len(res_store), num 1):
            res_store.append(i * res_store[i-1])
        return num * res_store[num-1]

Performance wise it will be very fast but it will store the result in list so it will take memory. For factorial 3000 -> size consumption will be 26040 bytes.