Python:有可能使这个尾部递归阶乘更快吗?

我正在为一个涉及组合数学的应用程序创建一个实用程序类。

我做了两个阶乘函数,它们是递归的尾部。第二种方法大大提高了计算组合数时的性能(我认为在英语中它们被称为 ,我使用C(n,k)表示法,并制作了一个nCk函数)。

所以我测量了时间,我实现了我的目标。我的新组合函数比新函数快得多。

但是当谈到阶乘函数时,我发现我的新阶乘函数“f”比第一个“fact”慢一点。

有没有办法使这个“f”函数的性能与“fact”一样好?

源代码

class Utils(object):
    """
    Class with useful functions
    """

    @staticmethod
    def fact(i, _current_factorial=1):
        '''
        The factorial function
        :param i: the number for calculating the factorial
        :param _current_factorial: for internal use, it is the acumulated product
        :return the result
        '''
        if i == 1:
            return _current_factorial
        else:
            return Utils.fact(i - 1, _current_factorial * i)

    @staticmethod
    def f(i, k=None, _current_factorial=1):
        '''
        The factorial function
        If k is given, it calculates the factorial but only with
        the k-th first numbers.
        Example:
            f(6) = 6 · 5 · 4 · 3 · 2 · 1
            f(6, 2) = 6 · 5
            f(6, 3) = 6 · 5 · 4
            f(9, 4) = 9 · 8 · 7 · 6
        :param i: the number for calculating the factorial
        :param k: optional, the number for calculating the factorial
        :param _current_factorial: for internal use, it is the acumulated product
        :return the result
        '''
        if k is None:
            k = i
        if i == 1 or k == 0:
            return _current_factorial
        else:
            return Utils.f(i - 1, k - 1, _current_factorial=_current_factorial * i)

    @staticmethod
    def C(n, k=1):
        '''
        Statistical combinations 'nCk'
        :param n: number of elements to be combined
        :param k: number of elements to be taken for each combination
        :return: the 'n choose k' mathematical result
        '''
        return Utils.fact(n) / (Utils.fact(k) * Utils.fact(n - k))

    @staticmethod
    def nCk(n, k=1):
        '''
        Statistical combinations 'nCk'
        :param n: number of elements to be combined
        :param k: number of elements to be taken for each combination
        :return: the 'n choose k' mathematical result
        '''
        return Utils.f(n, k) / Utils.f(k)



if __name__ == "__main__":
    NUM_TEST_ITERATIONS = 7500
    MAX_NUMBER_WITHOUT_STACKOVERFLOW = 998

    import time

    start = time.process_time()
    for i in range(NUM_TEST_ITERATIONS): Utils.f(MAX_NUMBER_WITHOUT_STACKOVERFLOW)
    elapsed = time.process_time() - start
    print('Function {} took {} to get result {}'.format('f', elapsed, Utils.f(MAX_NUMBER_WITHOUT_STACKOVERFLOW)))

    start = time.process_time()
    for i in range(NUM_TEST_ITERATIONS): Utils.fact(MAX_NUMBER_WITHOUT_STACKOVERFLOW)
    elapsed = time.process_time() - start
    print('Function {} took {} to get result {}'.format('fact', elapsed, Utils.fact(MAX_NUMBER_WITHOUT_STACKOVERFLOW)))

    start = time.process_time()
    for i in range(NUM_TEST_ITERATIONS): Utils.nCk(997, 4)
    elapsed = time.process_time() - start
    print('Function {} took {} to get result {}'.format('nCk', elapsed, Utils.nCk(997, 4)))

    start = time.process_time()
    for i in range(NUM_TEST_ITERATIONS): Utils.C(997, 4)
    elapsed = time.process_time() - start
    print('Function {} took {} to get result {}'.format('C', elapsed, Utils.C(997, 4)))

在屏幕上 :

Function f    took 7.854962716 to get result 402790050127220994538240674597601587306681545756471103647447357787726238637266286878923131618587992793273261872069265323955622495490298857759082912582527118115540044131204964883707335062250983503282788739735011132006982444941985587005283378024520811868262149587473961298417598644470253901751728741217850740576532267700213398722681144219777186300562980454804151705133780356968636433830499319610818197341194914502752560687555393768328059805942027406941465687273867068997087966263572003396240643925156715326363340141498803019187935545221092440752778256846166934103235684110346477890399179387387649332483510852680658363147783651821986351375529220618900164975188281042287183543472177292257232652561904125692525097177999332518635447000616452999984030739715318219169707323799647375797687367013258203364129482891089991376819307292252205524626349705261864003453853589870620758596211518646408335184218571196396412300835983314926628732700876798309217005024417595709904449706930796337798861753941902125964936412501007284147114260935633196107341423863071231385166055949914432695939611227990169338248027939843597628903525815803809004448863145157344706452445088044626373001304259830129153477630812429640105937974761667785045203987508259776060285826091261745049275419393680613675366264232715305430889216384611069135662432391043725998805881663054913091981633842006354699525518784828195856033032645477338126512662942408363494651203239333321502114252811411713148843370594801145777575035630312885989779863888320759224882127141544366251503974910100721650673810303577074640154112833393047276025799811224571534249672518380758145683914398263952929391318702517417558325636082722982882372594816582486826728614633199726211273072775131325222240100140952842572490801822994224069971613534603487874996852498623584383106014533830650022411053668508165547838962087111297947300444414551980512439088964301520461155436870989509667681805149977993044444138428582065142787356455528681114392680950815418208072393532616122339434437034424287842119316058881129887474239992336556764337968538036861949918847009763612475872782742568849805927378373244946190707168428807837146267156243185213724364546701100557714520462335084082176431173346929330394071476071813598759588818954312394234331327700224455015871775476100371615031940945098788894828812648426365776746774528000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Function fact took 6.757415364 to get result 402790050127220994538240674597601587306681545756471103647447357787726238637266286878923131618587992793273261872069265323955622495490298857759082912582527118115540044131204964883707335062250983503282788739735011132006982444941985587005283378024520811868262149587473961298417598644470253901751728741217850740576532267700213398722681144219777186300562980454804151705133780356968636433830499319610818197341194914502752560687555393768328059805942027406941465687273867068997087966263572003396240643925156715326363340141498803019187935545221092440752778256846166934103235684110346477890399179387387649332483510852680658363147783651821986351375529220618900164975188281042287183543472177292257232652561904125692525097177999332518635447000616452999984030739715318219169707323799647375797687367013258203364129482891089991376819307292252205524626349705261864003453853589870620758596211518646408335184218571196396412300835983314926628732700876798309217005024417595709904449706930796337798861753941902125964936412501007284147114260935633196107341423863071231385166055949914432695939611227990169338248027939843597628903525815803809004448863145157344706452445088044626373001304259830129153477630812429640105937974761667785045203987508259776060285826091261745049275419393680613675366264232715305430889216384611069135662432391043725998805881663054913091981633842006354699525518784828195856033032645477338126512662942408363494651203239333321502114252811411713148843370594801145777575035630312885989779863888320759224882127141544366251503974910100721650673810303577074640154112833393047276025799811224571534249672518380758145683914398263952929391318702517417558325636082722982882372594816582486826728614633199726211273072775131325222240100140952842572490801822994224069971613534603487874996852498623584383106014533830650022411053668508165547838962087111297947300444414551980512439088964301520461155436870989509667681805149977993044444138428582065142787356455528681114392680950815418208072393532616122339434437034424287842119316058881129887474239992336556764337968538036861949918847009763612475872782742568849805927378373244946190707168428807837146267156243185213724364546701100557714520462335084082176431173346929330394071476071813598759588818954312394234331327700224455015871775476100371615031940945098788894828812648426365776746774528000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Function nCk took 0.021283503999999454 to get result 40921610765.0
Function C   took 13.261998684000002   to get result 40921610765.0