为什么python中的递归如此缓慢?

So I was messing around in idle with recursion, and I noticed that a loop using recursion was much slower then a regular while loop, and I was wondering if anyone knew why. I have included the tests that I had done below:

所以我在用递归处理空闲时，我注意到使用递归的循环要比常规的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

During the last test however, I noticed that if I took out the else statement, it showed a slight improvement in speed, so I am wondering if the if statement is the cause of this loop speed difference?

但是在最后一次测试中，我注意到如果我取出else语句，它显示了速度的轻微提高，所以我想知道if语句是否是造成这个循环速度差异的原因?

2 个解决方案

#1

You've written your function to be tail recursive. In many imperative and functional languages, this would trigger tail recursion elimination, where the compiler replaces the CALL/RETURN sequence of instructions with a simple JUMP, making the process more or less the same thing as iteration, as opposed to the normal stack frame allocation overhead of recursive function calls. Python, however, does not use tail recursion elimination, as explained in some of these links:

您已经将函数写成tail递归的形式。在许多命令式和函数式语言中，这将触发尾递归消除，即编译器用一个简单的跳转替换指令的调用/返回序列，使过程或多或少与迭代相同，而不是递归函数调用的正常堆栈帧分配开销。但是，Python不使用尾部递归消除，如以下一些链接所述:

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

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

As you can see from the links, there are reasons it doesn't exist by default, and you can hack it in in a number of ways, but by default, Python prizes using things like generator functions to create complicated sequences of instructions, versus recursion.

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

#2

Recursion is fairly expensive compared to iteration (in general) because it requires the allocation of a new stack frame.

与迭代(通常)相比，递归是相当昂贵的，因为它需要分配一个新的堆栈框架。

#1