在Java中，以下是斐波那契函数的一个可能的尾部递归实现：

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

与标准递归实现形成对比：

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}

这意味着不需要将指令指针推到堆栈上，只需跳到递归函数的顶部并继续执行即可。这允许函数无限递归而不会溢出堆栈。

我写了一篇关于这个主题的博客文章，里面有堆栈框架的图形示例。

这个问题有很多很好的答案。。。但我忍不住提出了另一种看法，即如何定义“尾部递归”，或者至少是“正确的尾部递归”。即：是否应该将其视为程序中特定表达式的属性？还是应该将其视为编程语言实现的属性？

关于后一种观点，Will Clinger的一篇经典论文“正确的尾部递归和空间效率”（PLDI 1998）将“正确的尾递归”定义为编程语言实现的属性。该定义被构造为允许忽略实现细节（例如调用堆栈实际上是通过运行时堆栈还是通过堆分配的帧链接列表表示的）。

为了实现这一点，它使用了渐近分析：不是人们通常看到的程序执行时间，而是程序空间使用情况。这样，堆分配的链接列表与运行时调用堆栈的空间使用最终是渐近等价的；因此，人们会忽略编程语言实现的细节（这一细节在实践中当然非常重要，但当试图确定给定的实现是否满足“属性尾部递归”的要求时，可能会让事情变得一团糟）

该论文值得仔细研究，原因如下：

它给出了程序尾部表达式和尾部调用的归纳定义。（这样的定义，以及为什么这样的电话很重要，似乎是这里给出的大多数其他答案的主题。）以下是这些定义，只是为了提供文本的味道：定义1以核心方案编写的程序的尾部表达式归纳如下。lambda表达式的主体是尾部表达式如果（如果E0 E1 E2）是尾部表达式，则E1和E2都是尾部表达式。其他的都不是尾部表达式。定义2尾部调用是作为过程调用的尾部表达式。

（尾部递归调用，或者正如论文所说，“self-tail调用”是尾部调用的一种特殊情况，其中过程本身被调用。）

它为评估核心方案的六个不同“机器”提供了正式定义，其中每个机器都具有相同的可观察行为，除了每个机器所处的渐近空间复杂性类。例如，在为分别为1。基于堆栈的内存管理，2。垃圾收集，但没有尾部调用。垃圾收集和尾部调用，本文继续介绍更高级的存储管理策略，如4。“evlis尾部递归”，在尾部调用的最后一个子表达式参数求值期间不需要保存环境，5。将闭包的环境减少到该闭包的自由变量，以及6。Appel和Shao定义的所谓“空间安全”语义。为了证明这些机器实际上属于六个不同的空间复杂性类，本文针对每对被比较的机器，提供了程序的具体示例，这些程序将揭示一台机器上的渐近空间爆炸，而不是另一台机器。

（现在仔细阅读我的答案，我不确定我是否真的抓住了克林格论文的关键点。但是，唉，我现在不能花更多的时间来研究这个答案。）

考虑一个将前N个自然数相加的简单函数。（例如，和（5）＝0+1+2+3+4+5＝15）。

下面是一个使用递归的简单JavaScript实现：

function recsum(x) {
    if (x === 0) {
        return 0;
    } else {
        return x + recsum(x - 1);
    }
}

如果调用recsum（5），JavaScript解释器将评估以下内容：

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + (1 + recsum(0)))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15

请注意，在JavaScript解释器开始实际计算和之前，每个递归调用都必须完成。

下面是同一函数的尾部递归版本：

function tailrecsum(x, running_total = 0) {
    if (x === 0) {
        return running_total;
    } else {
        return tailrecsum(x - 1, running_total + x);
    }
}

以下是调用tailrecsum（5）时发生的事件序列（由于默认的第二个参数，它实际上是tailrecsum（5，0））。

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

在尾部递归情况下，每次对递归调用求值时，running_total都会更新。

注：原始答案使用了Python中的示例。由于Python解释器不支持尾部调用优化，这些代码已更改为JavaScript。然而，虽然尾部调用优化是ECMAScript 2015规范的一部分，但大多数JavaScript解释器不支持它。

如果每个递归情况仅由对函数本身的调用组成，并且可能具有不同的参数，则函数是尾部递归的。或者，尾部递归是没有待定工作的递归。注意，这是一个与编程语言无关的概念。

考虑定义如下的函数：

g(a, b, n) = a * b^n

一种可能的尾部递归公式是：

g(a, b, n) | n is zero = a
           | n is odd  = g(a*b, b,   n-1)
           | otherwise = g(a,   b*b, n/2)

如果您检查g（…）的每一个涉及递归情况的RHS，您会发现整个RHS都是对g（……）的调用，仅此而已。这个定义是尾部递归的。

作为比较，非尾部递归公式可能是：

g'(a, b, n) = a * f(b, n)
f(b, n) | n is zero = 1
        | n is odd  = f(b, n-1) * b
        | otherwise = f(b, n/2) ^ 2

f（…）中的每个递归情况都有一些需要在递归调用之后进行的未决工作。

注意，当我们从“g”到“g”时，我们充分利用了关联性（和交换性）乘法。这并不是偶然的，在大多数需要将递归转换为尾递归的情况下，都会利用这些财产：如果我们想急切地做一些工作，而不是让它等待，我们必须使用关联性之类的东西来证明答案是一样的。

尾部递归调用可以通过向后跳转来实现，而不是使用堆栈进行常规递归调用。注意，检测尾部呼叫或发出向后跳转通常很简单。然而，通常很难重新排列参数，以便向后跳转。由于此优化不是免费的，语言实现可以选择不实现此优化，或者通过使用“tailcall”指令标记递归调用和/或选择更高的优化设置来要求选择加入。

然而，某些语言（例如Scheme）确实需要所有实现来优化尾部递归函数，甚至可能需要所有尾部位置的调用。

在大多数命令式语言中，向后跳转通常被抽象为（while）循环，而尾部递归在优化为向后跳转时，与循环同构。

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

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个帧对象。）这会导致堆栈溢出错误。（嘿，这就是这个网站的名字来源！）

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

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