下面是比较两个函数的快速代码片段。第一种是传统的递归，用于求给定数的阶乘。第二种使用尾部递归。

理解起来非常简单直观。

判断递归函数是否为尾部递归函数的一种简单方法是，它是否在基本情况下返回具体值。这意味着它不会返回1或true或类似的值。它很可能会返回某个方法参数的变体。

另一种方法是判断递归调用是否没有任何加法、算术、修改等。这意味着它只是一个纯递归调用。

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

这本摘自《Lua编程》一书的摘录展示了如何进行正确的尾部递归（在Lua中，但也应适用于Lisp）以及为什么它更好。

尾部调用[尾部递归]是一种goto-dressed作为呼叫。当函数调用另一个作为其最后一个行动，所以它没有其他事情可做。例如在以下代码中，对g的调用是尾调用：函数f（x）返回g（x）终止在f调用g之后，它没有其他内容在这种情况下，程序不需要返回调用函数时调用的函数末端。因此在尾呼之后，程序不需要保留任何有关调用函数的信息在堆栈中。。。因为正确的尾呼使用no堆栈空间一个程序可以生成。例如，我们可以使用任意数字作为自变量；它永远不会溢出堆栈：函数foo（n）如果n>0，则返回foo（n-1）end终止…正如我前面所说的，尾呼是有点后顾之忧。因此，一个非常有用的正确的尾部调用在Lua用于编程状态机。此类应用程序可以代表功能状态；更改状态是去（或打电话）一个特定的作用例如，让我们考虑一个简单的迷宫游戏。迷宫有几个房间，每个房间最多四个门：北、南、东和西在每个步骤中，用户输入移动方向。如果有门在该方向上，用户将相应的房间；否则程序打印警告。目标是从最初的房间到最后的房间房间该游戏是典型的状态机，其中当前房间是状态。我们可以用一个每个房间的功能。我们用尾巴从一个房间移动到另一个有四个房间的小迷宫可能看起来像这样：功能室1（）本地移动=io.read（）如果移动==“南”，则返回房间3（）elseif move==“east”然后返回room2（）否则打印（“无效移动”）返回房间1（）--呆在同一个房间终止终止功能室2（）本地移动=io.read（）如果move==“south”，则返回room4（）elseif move==“west”然后返回房间1（）否则打印（“无效移动”）返回室2（）终止终止功能室3（）本地移动=io.read（）如果move==“north”，则返回room1（）elseif move==“east”然后返回room4（）否则打印（“无效移动”）返回室3（）终止终止功能室4（）打印（“恭喜！”）终止

因此，当您进行如下递归调用时：

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

这不是尾部递归的，因为在进行递归调用之后，您仍然需要在该函数中做一些事情（添加1）。如果输入的数字很高，可能会导致堆栈溢出。

为了理解尾部调用递归和非尾部调用递归之间的一些核心区别，我们可以探索这些技术的.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尾部调用条件。

尾部递归函数是一个递归函数，其中递归调用是函数中最后执行的事情。

常规递归函数，我们有堆栈，每次调用递归函数中的递归函数时，都会向调用堆栈添加另一层。在正常递归中空间：O（n）尾递归使空间复杂性从

O(N)=>O(1)

尾部调用优化意味着可以从另一个函数调用函数，而不增加调用堆栈。我们应该在递归解中编写尾部递归。但某些语言实际上不支持其引擎中的尾部递归，该引擎将语言向下编译。自从ecma6以来，规范中就有了尾部递归。但编译js的引擎都没有实现尾部递归。你无法在js中实现O（1），因为编译器本身不知道如何实现这种尾部递归。截至2020年1月1日，Safari是唯一支持尾部呼叫优化的浏览器。Haskell和Java具有尾部递归优化

正则递归阶乘

function Factorial(x) {
  //Base case x<=1
  if (x <= 1) {
    return 1;
  } else {
    // x is waiting for the return value of Factorial(x-1)
    // the last thing we do is NOT applying the recursive call
    // after recursive call we still have to multiply.
    return x * Factorial(x - 1);
  }
}

我们的调用堆栈中有4个调用。

Factorial(4); // waiting in the memory for Factorial(3)
4 * Factorial(3); //  waiting in the memory for Factorial(2)
4 * (3 * Factorial(2)); //  waiting in the memory for Factorial(1)
4 * (3 * (2 * Factorial(1)));
4 * (3 * (2 * 1));

我们正在进行4次Factorial（）调用，空间为O（n）这可能会导致堆栈溢出

尾部递归因子

function tailFactorial(x, totalSoFar = 1) {
  //Base Case: x===0. In recursion there must be base case. Otherwise they will never stop
  if (x === 0) {
    return totalSoFar;
  } else {
    // there is nothing waiting for tailFactorial to complete. we are returning another instance of tailFactorial()
    // we are not doing any additional computaion with what we get back from this recursive call
    return tailFactorial(x - 1, totalSoFar * x);
  }
}

在进行递归调用后，我们不需要记住任何内容

递归有两种基本类型：头部递归和尾部递归。

在头部递归中，函数进行递归调用，然后执行更多计算，可能使用例如递归调用。在尾部递归函数中，所有计算首先发生递归调用是最后发生的事情。

摘自这篇超棒的帖子。请考虑阅读它。

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

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

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

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