为什么python中的递归这么慢? [英] Why is recursion in python so slow?

问题描述

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

<预><代码>>>>导入时间>>>setu="""def test(x):x=x-1如果 x==0:返回 x别的:测试(x)""">>>setu2="""x=10当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如果 x==0:返回 x测试(x)""">>>timeit.timeit(stmt="test(10)",setup=setu,number=100)0.0006419437090698921

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

解决方案

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

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:

>>> 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?

解决方案

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:

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中的递归这么慢?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！