尝试实验macropy TCO实现的大小。

我发布了一个执行尾部调用优化(处理尾部递归和延续传递样式)的模块:https://github.com/baruchel/tco

优化Python中的尾递归

It has often been claimed that tail-recursion doesn't suit the Pythonic way of coding and that one shouldn't care about how to embed it in a loop. I don't want to argue with this point of view; sometimes however I like trying or implementing new ideas as tail-recursive functions rather than with loops for various reasons (focusing on the idea rather than on the process, having twenty short functions on my screen in the same time rather than only three "Pythonic" functions, working in an interactive session rather than editing my code, etc.).

在Python中优化尾递归实际上非常容易。虽然据说这是不可能的 或者非常棘手，我认为它可以通过优雅、简短和通用的解决方案来实现;我甚至 我认为大多数解决方案都没有使用Python的特性。 干净的lambda表达式与非常标准的循环一起工作，可以快速，高效和 用于实现尾递归优化的完全可用的工具。

出于个人方便，我编写了一个实现这种优化的小模块 通过两种不同的方式。我想在这里谈谈我的两个主要职能。

简单的方法:修改Y组合子

Y组合子是众所周知的;它允许在递归中使用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

该函数可以以以下方式使用;下面是两个尾部递归的例子 阶乘和Fibonacci的版本:

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

我认为计算一个表达式，即使很复杂，也比 求几个简单表达式的值，这是第二个版本中的情况。 我没有在我的模块中保留这个新函数，而且我没有看到它在任何情况下 可以用而不是“官方的”。

带有异常的延续传递样式

Here is a more general function; it is able to handle all tail-recursive functions, including those returning other functions. Recursive calls are recognized from other return values by the use of exceptions. This solutions is slower than the previous one; a quicker code could probably be written by using some special values as "flags" being detected in the main loop, but I don't like the idea of using special values or internal keywords. There is some funny interpretation of using exceptions: if Python doesn't like tail-recursive calls, an exception should be raised when a tail-recursive call does occur, and the Pythonic way will be to catch the exception in order to find some clean solution, which is actually what happens here...

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)被求为 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-08-29)。

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

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

在我看来，这个小函数最有趣的特点是，这个函数不依赖于一些肮脏的编程技巧，而仅仅是lambda微积分:当插入另一个lambda函数时，函数的行为会改变为另一个，它看起来非常像Y组合子。

基于Guido van Rossum关于该主题的陈述，CPython现在不支持，将来也可能永远不会支持尾部调用优化。

我听说过这样的说法，因为它修改堆栈跟踪的方式，使得调试更加困难。

不，而且永远不会，因为吉多·范·罗森更喜欢有正确的回溯

尾递归消去(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

尝试实验macropy TCO实现的大小。

在Python中，尾调用永远不能优化为跳转。优化是一种保留程序含义的程序转换。尾调用消除并不能保留Python程序的含义。

经常提到的一个问题是，尾部调用消除会改变调用堆栈，而Python允许运行时对堆栈进行内省。但还有一个问题很少被提及。在野外可能有很多这样的代码:

def map_file(path):
    f = open(path, 'rb')
    return mmap.mmap(f.fileno())

对mmap的调用。Mmap在尾部位置。如果它被跳转所取代，那么当前堆栈帧将在控制传递给mmap之前被丢弃。当前堆栈帧包含对文件对象的唯一引用，因此文件对象可以(在CPython中)在mmap被调用之前被释放，这将关闭文件描述符，在mmap看到它之前使其失效。

在最好的情况下，代码将失败并出现异常。在最坏的情况下，文件描述符可能在另一个线程中重用，导致mmap映射错误的文件。因此，这种“优化”对于大量现有的Python代码来说可能是灾难性的。

Python规范保证了这样的问题不会发生，所以可以肯定没有符合规范的实现将return f(args)转换为跳转——除非它有一个复杂的静态分析引擎，可以证明在这种情况下，早期丢弃一个对象不会产生可观察到的结果。

---

所有这些都不会阻止Python为带有跳转语义的显式尾部调用添加语法，例如

    return from f(args)

这不会破坏没有使用它的代码，而且它可能对自动生成的代码和一些算法有用。GvR不再是BDFL，所以它可能会发生，但我不会屏住呼吸。