Python：使用递归有效地确定因子和

Question

def sof (x, fact):
    if x % fact == 0:
        if fact >= x/fact:
            return fact + x/fact + sof (x,fact - 1)
        else:
            return 1
    else:
        return sof (x,fact-1)

如何使这个程序在运行时更高效？我个人已经没有什么想法了。在

Answer 1

I want to be able to run numbers over 4000 without exceeding my recursive limit

这里有一种方法可以使程序更高效，但不一定要更快。在代码中递归的基本情况：

if fact >= x // fact:

嵌套在余数检查中：

^{pr2}$

使您的代码能够继续检查不需要的数字。（例如，考虑一个大的素数*2，你的代码会一直检查直到fact达到1而不是中间点。）

对于这个算法在堆栈溢出之前可以处理的小数字来说，这不是一个速度问题。你只到了1999年堆栈溢出，而我的重新排列：

def sof(number, divisor):
    dividend = number // divisor

    if dividend > divisor:
        return 1

    if number % divisor:
        return sof(number, divisor - 1)

    return divisor + dividend + sof(number, divisor - 1)

使用相同的堆栈大小可以达到2086，因为它避免了那些额外的递归。在

当您通过sys.setrecursionlimit()扩展堆栈时，这种差异会增加。在