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

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

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

理解起来非常简单直观。

判断递归函数是否为尾部递归函数的一种简单方法是，它是否在基本情况下返回具体值。这意味着它不会返回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);
    }
}

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

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

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

一种简单的方法是：

  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），但没有一个调用向堆栈添加任何额外变量。因此编译器可以取消堆栈。

重要的一点是尾部递归本质上等同于循环。这不仅仅是一个编译器优化的问题，而是一个关于表现力的基本事实。这是双向的：你可以采取任何形式的循环

while(E) { S }; return Q

其中E和Q是表达式，S是语句序列，并将其转换为尾部递归函数

f() = if E then { S; return f() } else { return Q }

当然，必须定义E、S和Q来计算一些变量的有趣值。例如，循环函数

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

等效于尾部递归函数

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

（用参数较少的函数“包装”尾部递归函数是一种常见的函数习惯用法。）