考虑一个将前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解释器不支持它。

尾部递归是函数调用的递归函数自身位于函数的末尾（“尾部”），其中没有计算在递归调用返回后完成。许多编译器优化以将递归调用更改为尾部递归调用或迭代调用。

考虑计算一个数的阶乘的问题。

一种简单的方法是：

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

假设你调用阶乘（4）。递归树为：

       factorial(4)
       /        \
      4      factorial(3)
     /             \
    3          factorial(2)
   /                  \
  2                factorial(1)
 /                       \
1                       factorial(0)
                            \
                             1    

上述情况下的最大递归深度为O（n）。

但是，请考虑以下示例：

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

factTail（4）的递归树为：

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

这里，最大递归深度是O（n），但没有一个调用向堆栈添加任何额外变量。因此编译器可以取消堆栈。

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

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

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

许多人已经在这里解释了递归。我想引用Riccardo Terrell的《.NET中的并发性，并发和并行编程的现代模式》一书中关于递归的一些优点的一些想法：

“函数递归是FP中迭代的自然方式，因为它避免状态突变。在每次迭代期间，都会传递一个新值而不是被更新（变异）。在里面此外，可以编写递归函数，使您的程序更加模块化，并引入了开发机会并行化。"

以下是同一本书中关于尾部递归的一些有趣注释：

尾部调用递归是一种转换规则递归的技术函数转换为可处理大型输入的优化版本没有任何风险和副作用。注：尾部调用作为优化的主要原因是提高数据位置、内存使用率和缓存使用率。通过做尾巴调用时，被调用者使用与调用者相同的堆栈空间。这减少了记忆压力。它略微改善了缓存，因为存储器被后续调用方重用，并且可以留在缓存中，而不是驱逐旧的缓存线，为新的缓存腾出空间线

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