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

Question

因此，我在闲逛时使用了递归，我发现使用递归的循环比常规的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语句是否是造成循环速度差异的原因？

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会使用生成器函数之类的东西来创建复杂的指令序列，递归。