如何使我的阶乘函数更快更有效？

Question

我使用列表制作了阶乘计算函数

n = int(input("Enter a number: "))

def num2list(num):
    first = [int(i) for i in str(num)]
    return first

def multiplylists(x, y):
    listx = x
    listy = y
    value=0
    for n in range(len(listx)):
        for m in range(len(listy)):
            prod = listx[n]*listy[m]
            power=10**((len(listx)-n-1)+(len(listy)-m-1))
            value+=prod*power
    return(num2list(value))

def factorial(n):
    if n <= 1:
        return [1]

    return multiplylists(factorial(n-1), num2list(n))

print("the factorial of",n,"is",factorial(n))

这是一个大学项目，我认为教授的意图是使用类似于1000的列表来制作一个更快、更高效的阶乘函数

但是我的代码很慢，当number>；997

我犯了这样的错误

Enter a number: 1000
Traceback (most recent call last):
  File "part2.py", line 24, in <module>
    print("the factorial of",n,"is",factorial(n))
  File "part2.py", line 22, in factorial
    return multiplylists(factorial(n-1), num2list(n))
  File "part2.py", line 22, in factorial
    return multiplylists(factorial(n-1), num2list(n))
  File "part2.py", line 22, in factorial
    return multiplylists(factorial(n-1), num2list(n))
  [Previous line repeated 995 more times]
  File "part2.py", line 19, in factorial
    if n <= 1:
RecursionError: maximum recursion depth exceeded in comparison

我不知道当number>；997

Answer 1

只需简单地使其在O（n）中迭代运行即可

n = 500
facts = [1]*(n+1)
for i in range(1,n+1):
   facts[i] = facts[i-1]*(i)

print(facts[n])

Answer 2

由于最大递归深度，您将无法计算大于1000的阶乘（实际上更小，因为某些堆栈级别已被其他调用函数使用）

因此，您需要实现一种迭代方法。为了在列表中生成以数字表示的数字，将更容易以相反顺序存储数字，以便数字的索引对应于它乘以的10的幂。您可以在打印或返回结果时反转列表，以提高可读性

使用这种数字存储策略，乘法逻辑可以更加简单。您还应该使用Python的无限大整数（例如10**((len(listx)-n-1)+(len(listy)-m-1)）实现它而不进行“欺骗”：

def toDigits(n):
    result = []
    while n:
        n,d = divmod(n,10)
        result.append(d)
    return result or [0]

def multDigits(A,B):
    result = [0]
    for i,a in enumerate(A):
        for j,b in enumerate(B):
            p10,carry = i+j,a*b 
            while carry:
                if p10 >= len(result): result.append(0); continue
                carry,result[p10] = divmod(carry+result[p10],10)
                p10 += 1
    return result

def factorial(N):
    result = [1]
    for n in range(2,N+1):
        result = multDigits(result,toDigits(n))
    return result[::-1]

输出：

print(factorial(1000))

[4, 0, 2, 3, 8, 7, 2, 6, 0, 0, 7, 7, 0, 9, 3, 7, 7, 3, 5, ...


# proof that it works:

from math import factorial
digits = [ int(d) for d in str(factorial(1000)) ]
print(digits)

[4, 0, 2, 3, 8, 7, 2, 6, 0, 0, 7, 7, 0, 9, 3, 7, 7, 3, 5, ...

Answer 3

Python中的sys模块提供了一个名为setrecursionlimit()的函数来修改Python中的递归限制。它接受一个参数，即新递归限制的值

import sys 

sys.setrecursionlimit(10**6) 
def fact(n):  
    if(n == 0): 
        return 1 
    return n * fact(n - 1)