python中的慢递归

Question

我知道这个主题讨论得很好，但是我遇到了一个案例，我不太了解递归方法比使用“ reduce，lambda，xrange”的方法“更慢”。

def factorial2(x, rest=1):
    if x <= 1:
        return rest
    else:
        return factorial2(x-1, rest*x)


def factorial3(x):
    if x <= 1:
        return 1
    return reduce(lambda a, b: a*b, xrange(1, x+1))

我知道python不能优化尾递归，所以问题不在于此。据我了解，生成器仍应使用+1运算符生成n个数量的数字。所以从技术上讲，fact(n)应该n像递归一样加一个数。该lambda在reduce将被称为n时间就像递归方法......所以，既然我们没有尾巴调用优化在这两个情况下，堆栈将创建/销毁和返回n时间。并且if生成器中的a应该检查何时引发StopIteration异常。

这使我想知道为什么递归方法仍然比另一种方法慢，因为递归方法使用简单算术而不使用生成器。

在一个测试中，我用递归方法代替rest*x了x该方法，所花费的时间与使用的方法相比减少了reduce。

这是我的事实（400）的时间，1000次

factorial3：1.22370505333

factorial2：1.79896998405

编辑：

使方法从开始1到n都没有帮助，而不是从n开始1。因此，不会造成开销-1。

另外，我们可以使递归方法更快吗。我尝试了多种事情，例如可以更改的全局变量…使用可变上下文，方法是将变量放在可以像数组一样进行修改的单元格中，并保留不带参数的递归方法。将用于递归的方法作为参数发送，这样我们就不必在我们的范围内“取消引用”它了……？但是没有什么可以使它更快。

我要指出的是，我有一个事实，即使用一个forloop比这两种方法都快得多的事实，因此显然还有改进的空间，但是我不希望有什么比forloop更快的。

Answer 1

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

$ cat fact.py 
def factorial_recursive1(x):
    if x <= 1:
        return 1
    else:
        return factorial_recursive1(x-1)*x

def 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 code for now, we'll get back to it later in the answer
def range_prod(a, b):
    if a + 1 < b:
        c = (a+b)//2
        return range_prod(a, c) * range_prod(c, b)
    else:
        return a
def 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 loop
In [2]: %timeit factorial_recursive2(400)
10000 loops, best of 3: 90.9 µs per loop
In [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 loop
In [5]: %timeit factorial_divide_and_conquer(4000)
1000 loops, best of 3: 1.46 ms per loop
In [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 loop
In [9]: %timeit factorial_recursive2(4000)
100 loops, best of 3: 7.02 ms per loop