我发布了一个处理尾调用优化（同时处理尾递归和续延传递风格）的模块：https://github.com/baruchel/tco

优化Python的尾递归

人们经常声称尾递归不适合Pythonic风格的编码，并且不应该关心如何将其嵌入循环中。我不想争论这个观点；但有时，出于各种原因（关注思想而非过程，同时在屏幕上看到20个短函数而不仅仅是3个"Pythonic"函数，以交互式会话方式工作而非编辑代码等），我喜欢尝试或实现尾递归函数作为新的想法。

事实上，优化Python的尾递归很容易。虽然人们认为它是不可能或非常棘手的，但我认为可以使用优雅、短小和通用的解决方案实现；我甚至认为这些解决方案大多数都不使用Python特性。利用干净的lambda表达式与非常标准的循环结合使用，可以快速、高效且完全可用地实现尾递归优化工具。

出于个人方便，我编写了一个实现此优化的小模块，有两种不同的方法。我想在这里讨论我的两个主要功能。

清晰简洁的方法：修改Y组合子

Y组合子是众所周知的；它允许在递归的λ函数中使用λ函数，但不能允许将递归调用嵌入循环中。仅凭λ演算无法做到这一点。但是，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语句或可能更像传递样式的连续），这一点我必须承认。但是，再次，
我觉得有趣的是，请使用try，并且单行是一个return语句：我们尝试返回
一些东西（正常行为），但由于发生递归调用而无法执行（异常）。

初始答案（2013年8月29日）。

我编写了一个非常小的插件来处理尾递归。您可以在那里找到我的解释：https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs

它可以嵌入使用尾递归风格编写的lambda函数的另一个函数中，该函数将其评估为循环。

在这个小函数中，最有趣的功能（依我之见）是该函数不依赖于一些肮脏的编程黑科技，而是仅仅依赖于λ演算：当插入进另一个看起来很像Y组合符的lambda函数时，函数的行为就被改变了。

不，它永远不会，因为Guido van Rossum喜欢能够拥有正确的跟踪记录： 尾递归消除 (2009-04-22), 对于尾调用的最终言论 (2009-04-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

。