为什么python中的递归这么慢？

Question

因此我在使用递归进行空闲处理时,我注意到使用递归的循环比常规循环慢得多,我想知道是否有人知道原因.我已经包含了我在下面进行的测试:

>>> 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语句是否是这个循环速度差异的原因？

Answer 1

你已经编写了函数尾递归.在许多命令式和函数式语言中,这将触发尾递归消除,其中编译器用简单的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使用生成器函数之类的东西来创建复杂的指令序列,而不是递归.

Answer 2

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