尾部递归函数是一个递归函数，它在返回之前执行的最后一个操作是调用递归函数。也就是说，递归函数调用的返回值将立即返回。例如，您的代码如下所示：

def recursiveFunction(some_params):
    # some code here
    return recursiveFunction(some_args)
    # no code after the return statement

实现尾部调用优化或尾部调用消除的编译器和解释器可以优化递归代码以防止堆栈溢出。如果您的编译器或解释器没有实现尾部调用优化（例如CPython解释器），那么用这种方式编写代码不会有额外的好处。

例如，这是Python中的标准递归阶乘函数：

def factorial(number):
    if number == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        # Note that `number *` happens *after* the recursive call.
        # This means that this is *not* tail call recursion.
        return number * factorial(number - 1)

这是阶乘函数的尾调用递归版本：

def factorial(number, accumulator=1):
    if number == 0:
        # BASE CASE
        return accumulator
    else:
        # RECURSIVE CASE
        # There's no code after the recursive call.
        # This is tail call recursion:
        return factorial(number - 1, number * accumulator)
print(factorial(5))

（请注意，即使这是Python代码，CPython解释器也不会进行尾部调用优化，因此这样安排代码不会带来运行时的好处。）

您可能需要使代码更不可读，才能利用尾部调用优化，如阶乘示例所示。（例如，基本情况现在有点不直观，累加器参数被有效地用作一种全局变量。）

但尾部调用优化的好处是它可以防止堆栈溢出错误。（我会注意到，通过使用迭代算法而不是递归算法，您可以获得同样的好处。）

当调用堆栈推送了太多帧对象时，会导致堆栈溢出。当调用函数时，框架对象被推到调用堆栈上，当函数返回时，框架将从调用堆栈中弹出。框架对象包含诸如局部变量以及函数返回时要返回的代码行之类的信息。

如果递归函数进行了太多递归调用而没有返回，则调用堆栈可能会超出其帧对象限制。（数量因平台而异；在Python中默认为1000个帧对象。）这会导致堆栈溢出错误。（嘿，这就是这个网站的名字来源！）

但是，如果递归函数做的最后一件事是进行递归调用并返回其返回值，那么它就没有理由保持当前帧对象需要停留在调用堆栈上。毕竟，如果递归函数调用后没有代码，就没有理由挂起当前帧对象的局部变量。因此，我们可以立即删除当前帧对象，而不是将其保留在调用堆栈中。这样做的最终结果是，调用堆栈的大小不会增加，因此不会出现堆栈溢出。

编译器或解释器必须具有尾部调用优化功能，以便能够识别何时可以应用尾部调用优化。即使如此，您可能已经重新排列了递归函数中的代码，以利用尾部调用优化，这取决于您是否值得优化可读性的潜在降低。

为了理解尾部调用递归和非尾部调用递归之间的一些核心区别，我们可以探索这些技术的.NET实现。

这是一篇包含C#、F#和C++\CLI中的一些示例的文章：C#、F#和C++/CLI中的尾部递归冒险。

C#没有针对尾部调用递归进行优化，而F#进行了优化。

原理的差异涉及循环与Lambda演算。C#的设计考虑到了循环，而F#是基于Lambda演算的原理构建的。有关Lambda微积分原理的一本非常好（免费）的书，请参阅Abelson、Sussman和Sussman的《计算机程序的结构和解释》。

关于F#中的尾部调用，有关非常好的介绍性文章，请参阅F#中尾部调用的详细介绍。最后，这里有一篇文章介绍了非尾部递归和尾部调用递归（在F#中）之间的区别：尾部递归与F sharp中的非尾部递归。

如果您想了解C#和F#之间尾部调用递归的一些设计差异，请参阅在C#和F#中生成尾部调用操作码。

如果您非常想知道哪些条件阻止C#编译器执行尾部调用优化，请参阅本文：JIT CLR尾部调用条件。

在传统递归中，典型的模型是首先执行递归调用，然后获取递归调用的返回值并计算结果。通过这种方式，在每次递归调用返回之前，您不会得到计算结果。

在尾部递归中，首先执行计算，然后执行递归调用，将当前步骤的结果传递给下一个递归步骤。这导致最后一条语句的形式为（return（递归函数参数））。基本上，任何给定递归步骤的返回值都与下一个递归调用的返回值相同。

这样做的结果是，一旦准备好执行下一个递归步骤，就不再需要当前堆栈帧。这允许进行一些优化。事实上，使用一个适当编写的编译器，您永远不应该有带有尾部递归调用的堆栈溢出窃笑。只需在下一个递归步骤中重用当前堆栈帧。我很确定Lisp会这么做。

对我来说，理解尾调用递归的最好方法是递归的一种特殊情况，其中最后一个调用（或尾调用）是函数本身。

比较Python中提供的示例：

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^递归

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^尾部递归

正如您在常规递归版本中看到的，代码块中的最后一个调用是x+recsum（x-1）。所以在调用recsum方法之后，还有一个操作是x+。。。

然而，在尾部递归版本中，代码块中的最后一个调用（或尾部调用）是tailrecsum（x-1，running_total+x），这意味着最后一次调用是对方法本身进行的，之后不再进行操作。

这一点很重要，因为这里看到的尾部递归不会使内存增长，因为当底层VM看到一个函数在尾部位置（函数中要计算的最后一个表达式）调用自己时，它会消除当前堆栈帧，这就是所谓的尾部调用优化（TCO）。

EDIT

没有。请记住，上面的示例是用Python编写的，其运行时不支持TCO。这只是一个解释这一点的例子。在Scheme、Haskell等语言中支持TCO

与普通递归相比，尾部递归非常快。它很快，因为祖先调用的输出不会写入堆栈以保持跟踪。但在正常递归中，所有祖先调用堆栈中的输出以保持跟踪。

下面是一个使用尾部递归进行阶乘的常见Lisp示例。由于无堆栈的性质，人们可以进行疯狂的大型阶乘计算。。。

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

然后为了好玩，你可以尝试（格式化nil“~R”（！25））