这篇文章的问题是关于不同类型的递归是否具有不同的内存复杂性。文章的原因是，在Guido的Python History博客中，关于Python不支持尾递归消除（TRE）的评论引发了一系列关于在Python中添加TRE的讨论。在这篇文章中，Guido辩解了他不希望在Python语言中添加TRE的立场。他认为这样做是不符合Python风格的。他认为TRE不是Python的一部分，因此不应该被添加进来。

这篇文章还提到了关于BDsFL（Benevolent Dictator for Life）的问题。文章指出，即使是在一个有权威的决策者的委员会中，也不会对每个决策都感到满意。但至少你可以从BDsFL那里得到一个合理和有权威性的解释。

解决这个问题的方法是首先认识到不同类型的递归可能具有不同的内存复杂性。然后，根据具体情况选择适当的递归类型。例如，在一些情况下，尾递归可能是一个好的选择，因为它可以减少内存的使用。而在其他情况下，非尾递归可能更合适。最后，要考虑到语言本身的特点和设计原则，以决定是否添加尾递归消除功能。在这个例子中，Guido认为添加TRE不符合Python的设计原则和风格，因此拒绝了这个功能的添加。

总之，这篇文章讨论了不同类型的递归是否具有不同的内存复杂性这个问题，并解释了为什么在Python中不支持尾递归消除功能。文章提到了关于BDsFL的问题，并指出在决策过程中权威性的重要性。最后，文章提出了解决这个问题的方法，即根据具体情况选择适当的递归类型，并考虑到语言的设计原则和风格。

不同类型的递归是否具有不同的内存复杂度？

这个问题的出现是因为有人发现使用尾递归在Python中编码并不符合Pythonic的方式，也不需要关心如何将其嵌入到循环中。然而，有些人喜欢尝试或实现新的想法，将其作为尾递归函数而不是使用循环，出于各种原因（专注于思想而不是过程，同时在屏幕上显示二十个短函数而不只是三个“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)
fibo = bet( lambda f: lambda n,p,q: p if not n else f(n-1,q,p+q) )
fibo(10,0,1)

显然，递归深度不再是问题：

bet( lambda f: lambda n: 42 if not n else f(n-1) )(50000)

这当然是该函数的唯一真正目的。

这种优化只有一件事做不到：它不能用于将求值为另一个函数的尾递归函数（这是因为可调用的返回对象都被视为没有区别的进一步递归调用）。由于我通常不需要这样的功能，所以对于上述代码我非常满意。然而，为了提供一个更通用的模块，我考虑了一下如何解决这个问题（见下一节）。

关于这个过程的速度（虽然这不是真正的问题），它是相当好的；尾递归函数的评估甚至比使用更简单表达式的以下代码更快：

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)

当然，可以提出一个反对意见，即异常不应该用于有意地重新定向解释器（作为一种goto语句或可能是一种延续传递样式），我必须承认这一点。但是，我觉得使用单行的return语句进行尝试很有趣：我们尝试返回一些东西（正常行为），但由于发生了递归调用（异常），所以我们无法这样做。

最初的回答（2013-08-29）。

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

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

这个小函数中最有趣的特点，在我个人的意见中，是函数不依赖于一些肮脏的编程技巧，而是依赖于纯粹的lambda演算：将函数的行为更改为在插入另一个lambda函数中时的行为，这个函数看起来非常像Y组合子。

您是否可以提供一个通过某些条件基于某些条件来定义函数的示例（最好是类似于正常定义的方式），该函数在这种情况下尾调用了多个其他函数之一？此外，您的包装函数bet0是否可以用作类方法的装饰器？

我不确定我是否可以在评论中以块样式编写代码，但是您当然可以使用def语法编写您的函数，实际上上面的最后一个示例依赖于条件。在我的文章baruchel.github.io/python/2015/11/07/…中，您可以看到一个段落，开始于“Of course you could object that nobody would write such a code”，其中我给出了一个使用常规定义语法的示例。关于您问题的第二部分，我需要再考虑一下，因为我已经有一段时间没有在这方面花时间了。谢谢。您应该在函数中关注递归调用发生的位置，即使您使用的是非尾调用优化的语言实现。这是因为递归调用之后发生的部分是需要存储在堆栈上的部分。因此，使函数尾递归最小化每次递归调用需要存储的信息量，这样您就可以在需要时拥有更大的递归调用堆栈空间。

不同类型的递归是否具有不同的内存复杂度？

这个问题出现的原因是Guido van Rossum喜欢能够拥有正确的回溯。他在2009年的两篇文章中提到了尾递归消除的概念。尾递归消除是一种手动消除递归的方法，可以通过转换递归函数为循环来实现。下面是一个示例代码：

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

或者可以使用`reduce`函数来进行转换，如下所示：

from operator import add
reduce(add, xrange(n + 1), csum)

尾递归消除对于一般情况下的尾递归都是有效的。

有人对这个设计决策提出了批评，认为这是一个愚蠢的设计决策。然而，这个决策主要是基于调试的考虑。有人认为尾递归是一种优雅的解决问题的方法，但拒绝支持它是因为语法不符合“Pythonic”的风格。

还有一些人提出了一些支持尾递归的重要论点。首先，有些算法非递归表达起来非常困难，以至于用非递归的方式编写它们是不实际的（例如Karatsuba乘法）。其次，即使语言不支持尾调用优化，尾递归仍然应该优先考虑，因为它可以最小化每个递归调用在堆栈上的大小。

关于使用`while True`的问题，它会一直循环直到遇到`return`语句才会跳出循环。需要注意的是，当`n`为负数时，循环会无限执行。

另外，这种`while True`循环只适用于直接调用自身的函数，对于相互递归的调用或使用高阶代码（如传递函数参数）的情况不适用。