为什么Python中的递归很慢？

Question

我在使用递归时在idle中进行了一些尝试，注意到使用递归的循环比普通的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语句导致了这个循环速度的差异？

- IT Ninja

---

Python在函数调用方面有一定的开销，但你可以通过使用while循环来避免这种情况。 - mgilson

递归与迭代相比，在Python和C中总是较慢的。请查看尾递归。 - Ashwini Chaudhary

Python中没有尾递归优化：http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html - acjay

Answer 1

你已经将函数写成了尾递归形式。在许多命令式和函数式语言中，这会触发尾递归消除，编译器会用简单的跳转指令JUMP替换调用/返回序列的指令，使得过程与迭代的基本相同，而不像递归函数调用那样需要正常的堆栈帧分配开销。然而，Python并不使用尾递归消除，如下面的链接所解释的: http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html http://metapython.blogspot.com/2010/11/tail-recursion-elimination-in-python.html 从这些链接中可以看出，它默认情况下不存在的原因，你可以通过多种方式进行修改，但是Python更喜欢使用生成器函数来创建复杂的指令序列，而不是使用递归。

- acjay

Answer 2

相对于迭代而言，递归在一般情况下比较消耗资源，因为它需要分配一个新的栈帧。

- Anoop Vaidya