python中的慢递归

python中的慢递归

递归版本的速度较慢是由于需要在每次调用时解析命名（自变量）变量。我提供了一种不同的递归实现，该实现仅具有一个参数，并且运行速度稍快。

$ cat fact.py def factorial_recursive1(x):    if x <= 1:        return 1    else:        return factorial_recursive1(x-1)*xdef factorial_recursive2(x, rest=1):    if x <= 1:        return rest    else:        return factorial_recursive2(x-1, rest*x)def factorial_reduce(x):    if x <= 1:        return 1    return reduce(lambda a, b: a*b, xrange(1, x+1))# Ignore the rest of the pre for now, we'll get back to it later in the answerdef range_prod(a, b):    if a + 1 < b:        c = (a+b)//2        return range_prod(a, c) * range_prod(c, b)    else:        return adef factorial_divide_and_conquer(n):    return 1 if n <= 1 else range_prod(1, n+1)$ ipython -i fact.py In [1]: %timeit factorial_recursive1(400)10000 loops, best of 3: 79.3 µs per loopIn [2]: %timeit factorial_recursive2(400)10000 loops, best of 3: 90.9 µs per loopIn [3]: %timeit factorial_reduce(400)10000 loops, best of 3: 61 µs per loop

由于在您的示例中涉及到非常多的数字，因此最初我怀疑性能差异可能是由于乘法顺序造成的。在每次迭代中，将一个较大的部分乘积乘以下一个数字，该乘积与乘积中的位数/位数成比例，因此这种方法的时间复杂度为O（n
2），其中n是最终位数产品。相反，最好使用分治法，其中最终结果是两个近似相等的长值的乘积，每个值以相同的方式递归计算。所以我也实现了那个版本（参见

factorial_divide_and_conquer(n)

上面的代码）。如您在下面看到的，它仍然输给了

reduce()

小参数的基于版本的版本（由于命名参数存在相同的问题），但对于大参数则优于。

In [4]: %timeit factorial_divide_and_conquer(400)10000 loops, best of 3: 90.5 µs per loopIn [5]: %timeit factorial_divide_and_conquer(4000)1000 loops, best of 3: 1.46 ms per loopIn [6]: %timeit factorial_reduce(4000)100 loops, best of 3: 3.09 ms per loop

更新

尝试运行符合默认递归限制的

factorial_recursive?()

版本

x=4000

，因此必须增加该限制：

In [7]: sys.setrecursionlimit(4100)In [8]: %timeit factorial_recursive1(4000)100 loops, best of 3: 3.36 ms per loopIn [9]: %timeit factorial_recursive2(4000)100 loops, best of 3: 7.02 ms per loop