Python是否优化尾递归？
我有以下代码失败，出现以下错误：
RuntimeError：超过最大递归深度
我试图重写这个以允许尾递归优化（TCO）。 我相信，如果TCO发生，这个代码应该是成功的。
def trisum(n, csum):
if n == 0:
return csum
else:
return trisum(n - 1, csum + n)
print(trisum(1000, 0))
我应该得出结论：Python不会做任何类型的TCO，或者我只需要以不同的方式定义它？
不，并且它从不会因为Guido喜欢能够有适当的回溯
http://neopythonic.blogspot.com.au/2009/04/tail-recursion-elimination.html
http://neopythonic.blogspot.com.au/2009/04/final-words-on-tail-calls.html
您可以使用像这样的转换手动消除递归
>>> 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
编辑（2015-07-02）：随着时间的推移，我的回答变得相当流行，因为它最初更多的是一个链接，而不是其他任何东西，我决定花一些时间并重写它（但是，最初的答案可以在最后找到）。
编辑（2015-07-12）：我终于发布了一个模块来执行尾部调用优化（处理尾部递归和延续传递样式）：https：//github.com/baruchel/tco
在Python中优化尾部递归
人们经常声称，尾递归不适合pythonic编码方式，并且不应该关心如何将其嵌入到循环中。 我不想用这个观点来争论; 有时候，我喜欢尝试或实现新的想法作为尾递归函数，而不是循环出于各种原因（侧重于想法而不是过程，在同一时间在屏幕上显示20个简短函数，而不仅仅是三个“pythonic”功能，在交互式会话中工作而不是编辑我的代码等）。
在Python中优化尾递归实际上非常简单。 虽然它被认为是不可能的或非常棘手的，但我认为它可以通过优雅，简短和一般的解决方案来实现; 我甚至认为，大多数这些解决方案并不使用Python功能，除非他们应该这样做。 清理lambda表达式与非常标准的循环一起工作，可以实现快速，高效且完全可用的工具来实现尾递归优化。
为了个人的方便，我写了一个小模块，通过两种不同的方式实现这种优化。 我想在这里讨论我的两个主要功能。
干净的方式：修改Y组合器
Y组合器是众所周知的; 它允许以递归方式使用lambda函数，但它本身不允许在循环中嵌入递归调用。 Lambda微积分本身不能做这样的事情。 然而，Y组合器稍微改变就可以保护实际评估的递归调用。 因此可以延迟评估。
这是Y组合器的着名表达式：
lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))
随着非常微小的变化，我可以得到：
lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args)))
函数f现在不用调用自己，而是返回一个执行完全相同调用的函数，但是由于它返回，所以可以稍后从外部进行评估。
我的代码是：
def bet(func):
b = (lambda f: (lambda x: x(x))(lambda y:
f(lambda *args: lambda: y(y)(*args))))(func)
def wrapper(*args):
out = b(*args)
while callable(out):
out = out()
return out
return wrapper
该功能可以通过以下方式使用; 这里有两个例子，它们是阶乘和斐波那契的尾递归版本：
>>> from recursion import *
>>> fac = bet( lambda f: lambda n, a: a if not n else f(n-1,a*n) )
>>> fac(5,1)
120
>>> fibo = bet( lambda f: lambda n,p,q: p if not n else f(n-1,q,p+q) )
>>> fibo(10,0,1)
55
显然，递归深度不再是问题：
>>> bet( lambda f: lambda n: 42 if not n else f(n-1) )(50000)
42
这当然是该功能的唯一真正目的。
这种优化只能做一件事：它不能用于对另一个函数进行求值的尾递归函数（这是来自于可调用的返回对象全部作为进一步的递归调用进行处理而没有区别的事实）。 由于我通常不需要这样的功能，所以我对上面的代码非常满意。 然而，为了提供一个更通用的模块，我想了解更多，以便为这个问题找到一些解决方法（请参阅下一节）。
关于这个过程的速度（然而这不是真正的问题），它恰好是相当好的; 尾递归函数甚至比使用更简单的表达式的下面的代码更快地被评估：
def bet1(func):
def wrapper(*args):
out = func(lambda *x: lambda: x)(*args)
while callable(out):
out = func(lambda *x: lambda: x)(*out())
return out
return wrapper
我认为评估一个表达式，甚至是复杂的，比评估几个简单的表达式要快得多，这在第二个版本中就是这种情况。 我没有将这个新功能保留在我的模块中，我也没有看到可以使用它而不是“官方”的情况。
继续传球与例外
这是一个更普遍的功能; 它能够处理所有的尾递归函数，包括那些返回其他函数的函数。 递归调用通过使用异常从其他返回值中识别。 这个解决方案比前一个更慢; 通过在主循环中检测到“标志”，可以使用一些特殊值编写更快的代码，但我不喜欢使用特殊值或内部关键字的想法。 使用异常有一些有趣的解释：如果Python不喜欢尾递归调用，当发生尾递归调用时应该引发异常，pythonic方法将捕获异常以找到一些干净解决方案，这实际上是在这里发生的......
class _RecursiveCall(Exception):
def __init__(self, *args):
self.args = args
def _recursiveCallback(*args):
raise _RecursiveCall(*args)
def bet0(func):
def wrapper(*args):
while True:
try:
return func(_recursiveCallback)(*args)
except _RecursiveCall as e:
args = e.args
return wrapper
现在可以使用所有功能。 在下面的例子中， f(n)的任何正值， f(n)被评估为标识函数：
>>> f = bet0( lambda f: lambda n: (lambda x: x) if not n else f(n-1) )
>>> f(5)(42)
42
当然，有人可能会认为，例外情况并不打算用于意图重定向解释者（作为一种goto陈述或可能是一种延续传球方式），我不得不承认。 但是，我觉得有趣的是，使用单行作为return语句来try使用try ：我们试图返回某些东西（正常行为），但由于递归调用发生（异常），我们无法做到这一点。
初步答复（2013-08-29）。
我写了一个非常小的插件来处理尾递归。 您可以在我的解释中找到它：https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs
它可以在另一个函数中嵌入一个用尾递归样式编写的lambda函数，并将其评估为循环。
在我看来，这个小函数中最有趣的特性是该函数不依赖于某些脏编程攻击，而仅仅依赖于lambda演算：当插入到另一个lambda函数中时，该函数的行为被更改为另一个函数看起来非常像Y-combinator。
问候。
Guido的这个词在http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html
我最近在我的Python历史博客中发布了一篇关于Python功能特性起源的条目。 关于不支持尾递归消除（TRE）的一句话立即引发了一些关于Python不会这么做的遗憾的评论，包括其他人尝试“证明”TRE可以添加到Python中的最近博客条目的链接容易。 所以让我捍卫自己的立场（这是我不希望TRE的语言）。 如果你想要一个简短的答案，那简直就是和谐。 这是一个很长的答案：
链接地址: http://www.djcxy.com/p/80667.html上一篇: Does Python optimize tail recursion?
下一篇: Why inline static type resolution does not work on List?