14

所以我在递归闲置中搞砸了，我注意到使用递归的循环比常规的 while 循环慢得多，我想知道是否有人知道为什么。我已经包括了我在下面所做的测试：

>>> import timeit
>>> setu="""def test(x):
    x=x-1
    if x==0:
        return x
    else:
        test(x)
    """
>>> setu2="""
x=10
while x>0:
    x=x-1
"""
>>> timeit.timeit(stmt="test(10)",setup=setu,number=100)
0.0006629826315997432
>>> timeit.timeit(stmt=setu2,number=100)
0.0002488750590750044
>>> setu="""def test(x):
    x=x-1
    if x==0:
        return x
    test(x)
    """
>>> timeit.timeit(stmt="test(10)",setup=setu,number=100)
0.0006419437090698921

然而，在最后一次测试中，我注意到如果我取出else语句，它显示速度略有提高，所以我想知道 if 语句是否是导致这种循环速度差异的原因？

4

2 回答 2

24

您已将函数编写为尾递归。在许多命令式和函数式语言中，这将触发尾递归消除，其中编译器用简单的 JUMP 替换 CALL/RETURN 指令序列，使过程或多或少与迭代相同，而不是正常的堆栈帧分配递归函数调用的开销。但是，Python 不使用尾递归消除，如其中一些链接中所述：

http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

http://metapython.blogspot.com/2010/11/tail-recursion-elimination-in-python.html

正如您从链接中看到的那样，默认情况下它不存在是有原因的，您可以通过多种方式破解它，但默认情况下，Python 奖励使用生成器函数之类的东西来创建复杂的指令序列，而不是递归。

于 2012-11-24T16:48:05.943 回答
4

与迭代（通常）相比，递归相当昂贵，因为它需要分配新的堆栈帧。

于 2012-11-24T16:20:45.000 回答