Как сделать мою факториальную функцию более быстрой и эффективной?

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!

но мой код работает медленно, и когда число> 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

я не знаю, почему мой код ошибка, когда число> 997

Answer 1

Модуль sys в Python предоставляет функцию setrecursionlimit() для изменения ограничения рекурсии в Python. Требуется один параметр, значение нового лимита рекурсии.

import sys 

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

Answer 2

Просто сделайте итеративным запуск за 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 3

Из-за максимальной глубины рекурсии вы не сможете вычислить факториалы больше 1000 (на самом деле меньше, потому что некоторые уровни стека уже используются другими вызывающими функциями)

Поэтому вам необходимо реализовать итеративный подход . Чтобы получить числа, выраженные в виде цифр в списке, будет проще хранить цифры в обратном порядке, чтобы индекс di git соответствовал степени 10, на которую оно умножается. Вы можете перевернуть список для удобства чтения при печати или при возврате результата.

С этой стратегией хранения di git умножение logi c может быть более простым. Вы также должны реализовать это без «обмана» с помощью целых чисел бесконечного размера 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]

output:

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 4

def fact(n):
if n==0:
    return 1
else:
    return (n * fact(n-1))


 x=fact(1000)
print(x)