Python 是否优化了尾递归? [英] Does Python optimize tail recursion?

问题描述

我有以下代码失败并出现以下错误:

<块引用>

运行时错误:超出最大递归深度

我试图重写它以允许尾递归优化 (TCO).我相信如果发生 TCO，此代码应该会成功.

def trisum(n, csum):如果 n == 0:返回总和别的:返回 trisum(n - 1, csum + n)打印(三和(1000，0))

我是否应该得出结论，Python 不承担任何类型的 TCO，还是我只需要对其进行不同的定义?

解决方案

不，它永远不会，因为 Guidovan Rossum 更喜欢能够有适当的回溯:

尾递归消除 (2009-04-22)

尾调用的最后一句话 (2009-04-27)

您可以通过这样的转换手动消除递归:

<预><代码>>>>def trisum(n, csum):... while True: # 将递归改为while循环...如果 n == 0:...返回总和... n, csum = n - 1, csum + n # 更新参数而不是尾递归>>>三和(1000,0)500500

I have the following piece of code which fails with the following error:

RuntimeError: maximum recursion depth exceeded

I attempted to rewrite this to allow for tail recursion optimization (TCO). I believe that this code should have been successful if a TCO had taken place.

def trisum(n, csum):
    if n == 0:
        return csum
    else:
        return trisum(n - 1, csum + n)

print(trisum(1000, 0))

Should I conclude that Python does not do any type of TCO, or do I just need to define it differently?

解决方案

No, and it never will since Guido van Rossum prefers to be able to have proper tracebacks:

Tail Recursion Elimination (2009-04-22)

Final Words on Tail Calls (2009-04-27)

You can manually eliminate the recursion with a transformation like this:

>>> def trisum(n, csum):
...     while True:                     # Change recursion to a while loop
...         if n == 0:
...             return csum
...         n, csum = n - 1, csum + n   # Update parameters instead of tail recursion

>>> trisum(1000,0)
500500

这篇关于Python 是否优化了尾递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！