我有下面这段代码，执行时出现以下错误：
RuntimeError: maximum recursion depth exceeded
我尝试对其进行重写以允许尾递归优化(TCO)。如果发生了TCO，我相信这段代码应该会成功。
def trisum(n, csum):
if n == 0:
return csum
else:
return trisum(n - 1, csum + n)
print(trisum(1000, 0))
我是否应该得出结论，Python不执行任何类型的TCO，还是我只需要以不同的方式定义它？
尾递归消除（2009年4月22日）
关于尾调用的最后话（2009年4月27日）
您可以通过像这样的转换手动消除递归：
>>> 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
from operator import add; reduce(add, xrange(n + 1), csum)？ - Jon Clements我发布了一个实现尾调用优化的模块（同时处理尾递归和延续传递风格）：https://github.com/baruchel/tco
经常有人声称，尾递归不适合Python式编程方式，而且不应该关心如何将其嵌入循环中。我不想就这个观点争论；但是有时候为了各种原因（专注于思路而不是过程，屏幕上同时显示二十个短函数而不是三个“Pythonic”函数，使用交互式会话而不是编辑代码等）我喜欢尝试或者实现新的想法作为尾递归函数，而不是用循环。
实际上，在Python中优化尾递归非常容易。虽然有人认为它是不可能或者非常棘手的，但我认为可以通过优雅、简洁和通用的解决方案来实现；甚至大多数解决方案不使用Python特性，而是使用非常标准的循环和干净的lambda表达式，从而实现快速、高效和完全可用的工具来实现尾递归优化。
出于个人方便，我编写了一个小模块来实现这种优化的两种不同方式。在这里，我想讨论一下我的两个主要函数。
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
现在可以使用所有函数。在下面的例子中，对于任何正值n，f(n)都会被计算为恒等函数：
>>> f = bet0( lambda f: lambda n: (lambda x: x) if not n else f(n-1) )
>>> f(5)(42)
42
当然，可以说异常并不是用于有意地重定向解释器（作为一种类似于goto语句或可能更像 continuation passing style的语句），我得承认。但是，再次强调，我觉得使用单行代码的try语句来实现return语句很有趣：我们试图返回某些东西（正常行为），但由于发生递归调用（异常），我们无法实现。
初始回答（2013-08-29）。
我编写了一个非常小的插件来处理尾递归。您可以在我的解释中找到它：https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs
它可以将使用尾递归风格编写的lambda函数嵌入到另一个函数中，该函数将其评估为循环。
在我看来，这个小函数中最有趣的特点是，它不依赖于某些肮脏的编程技巧，而是仅依赖于lambda演算：当插入到另一个非常类似于Y组合子的lambda函数中时，函数的行为会改变为另一个函数。
bet0是否可以用作类方法的装饰器？ - Alexeydef 语法来定义函数，实际上上面的最后一个示例依赖于条件。在我的博客文章 http://baruchel.github.io/python/2015/11/07/explaining-functional-aspects-in-python/ 中，你可以看到一个段落开头是“当然，你可能会反对没有人会编写这样的代码”，在那里我给出了一个通常的定义语法的示例。关于你问题的第二部分，我需要再考虑一下，因为我已经有一段时间没有涉及它了。问候。 - Thomas BaruchelGuido的话在http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html
我最近在我的Python History博客上发布了一篇关于Python功能特性起源的文章。有关不支持尾递归消除(TRE)的侧面评论立即引起了几条评论，包括其他人尝试“证明”可以轻松地将TRE添加到Python的最近博客条目的链接。因此，让我捍卫我的立场(我不希望语言中有TRE)。如果你想要一个简短的答案，那就是unpythonic。以下是详细的解释:
CPython 不支持尾调用优化，基于Guido van Rossum 对此的声明，可能永远不会支持。
有人认为这会使得调试更加困难，因为它会修改堆栈跟踪信息。
在Python中，尾调用永远不能被优化为跳转。优化是一种保留程序含义的程序转换。尾调用消除不会保留Python程序的含义。
经常提到的一个问题是，尾调用消除改变了调用堆栈，并且Python允许运行时检查堆栈。但很少提到另一个问题。在野外可能有很多这样的代码：
def map_file(path):
f = open(path, 'rb')
return mmap.mmap(f.fileno())
mmap.mmap 的代码处于尾部位置。如果它被替换为跳转，则在控制权传递给 mmap 之前，当前的堆栈帧将被丢弃。当前的堆栈帧包含对文件对象的唯一引用，因此在调用 mmap 之前，文件对象可能会（在 CPython 中）被释放，从而关闭文件描述符，使其在 mmap 查看之前无效。mmap 映射错误的文件。因此，这种“优化”将是对现有 Python 代码巨大的潜在灾难。return f(args) 转换为跳转。
return from f(args)
这不会破坏没有使用它的代码，对于自动生成的代码和某些算法可能很有用。GvR不再是BDFL，所以这可能会发生，但我不会抱太大希望。
在Python中没有内置的尾递归优化。然而，我们可以通过抽象语法树（AST）“重建”函数，在那里消除递归并用循环替换它。Guido是绝对正确的，这种方法有一些局限性，所以我不能推荐它使用。
然而，我仍然编写了自己版本的优化器（更像是一个训练示例），你甚至可以尝试它的工作方式。
通过pip安装这个包：
pip install astrologic
from astrologic import no_recursion
counter = 0
@no_recursion
def recursion():
global counter
counter += 1
if counter != 10000000:
return recursion()
return counter
print(recursion())
这个解决方案不稳定，您绝不能在生产环境中使用它。您可以阅读关于GitHub页面上的一些重要限制（抱歉，页面是俄语）。然而，这个解决方案相当“真实”，没有中断代码和其他类似的技巧。
除了优化尾递归，你还可以通过以下方式手动设置递归深度：
import sys
sys.setrecursionlimit(5500000)
print("recursion limit:%d " % (sys.getrecursionlimit()))
return func(...)（无论是否递归）的情况。TCO 是 TRE 的超集，更为实用（例如，它使得 CPS 可行，而 TRE 不能），且实现难度不大。 - user395760foo函数内又调用了一次foo函数，然后再从一个foo函数内部调用另一个foo函数...... 在失去这个信息后，并不会丢失任何有用的信息。 - Kevin