什么是尾递归？

我将解释简单递归函数和尾递归函数

为了编写一个简单的递归函数

要考虑的第一点是何时应该决定退出循环，即if循环

第二个是如果我们是我们自己的职能，该怎么办

从给定的示例：

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

从上面的例子

if(n <=1)
     return 1;

是何时退出循环的决定因素

else 
     return n * fact(n-1);

是否要进行实际处理

为了便于理解，让我一个接一个地完成任务。

让我们看看如果我跑步会在内部发生什么 fact(4)

代入n = 4

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

If循环失败，因此进入else循环，因此返回4 * fact(3)

在堆栈内存中，我们有 4 * fact(3)

代入n = 3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

If循环失败，因此进入else循环

所以它返回 3 * fact(2)

记住我们称呼为``4 * fact（3）``

输出为 fact(3) = 3 * fact(2)

到目前为止，堆栈已经 4 * fact(3) = 4 * 3 * fact(2)

在堆栈内存中，我们有 4 * 3 * fact(2)

代入n = 2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

If循环失败，因此进入else循环

所以它返回 2 * fact(1)

记得我们打过电话 4 * 3 * fact(2)

输出为 fact(2) = 2 * fact(1)

到目前为止，堆栈已经 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

在堆栈内存中，我们有 4 * 3 * 2 * fact(1)

代入n = 1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If 循环为真

所以它返回 1

记得我们打过电话 4 * 3 * 2 * fact(1)

输出为 fact(1) = 1

到目前为止，堆栈已经 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

最后，fact（4）的结果= 4 * 3 * 2 * 1 = 24

在尾递归会

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}

代入n = 4

public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

If循环失败，因此进入else循环，因此返回fact(3, 4)

在堆栈内存中，我们有 fact(3, 4)

代入n = 3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

If循环失败，因此进入else循环

所以它返回 fact(2, 12)

在堆栈内存中，我们有 fact(2, 12)

代入n = 2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

If循环失败，因此进入else循环

所以它返回 fact(1, 24)

在堆栈内存中，我们有 fact(1, 24)

代入n = 1

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

If 循环为真

所以它返回 running_total

输出为 running_total = 24

最后，fact（4,1）= 24的结果

为了理解尾调用递归和非尾调用递归之间的一些核心差异,我们可以探索这些技术的.NET实现.

下面是一篇文章,其中包含C#,F#和C++\CLI中的一些示例:C#,F#和C++\CLI 中的Tail Recursion中的冒险.

C#不优化尾调用递归,而F#则优化.

原理的差异涉及循环与Lambda演算.C#的设计考虑了循环,而F#是根据Lambda演算的原理构建的.有关Lambda演算原理的非常好(和免费)的书,请参阅Abelson,Sussman和Sussman的计算机程序的结构和解释.

关于F#中的尾部调用,有关非常好的介绍性文章,请参阅F#中的尾部调用详细介绍.最后,这篇文章涵盖了非尾递归和尾调用递归(在F#中)之间的区别:F sharp中的尾递归与非尾递归.

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

如果您非常关心要知道哪些条件阻止C#编译器执行尾调用优化,请参阅本文:JIT CLR尾调用条件.

一尾递归函数是一个递归函数，其中最后一个动作恢复之前它使递归函数调用。即，立即返回递归函数调用的返回值。例如，您的代码如下所示：

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解释器也不会进行尾调用优化，因此按这种方式排列代码不会给运行时带来任何好处。）

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

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

当调用堆栈中放入过多帧对象时，会导致堆栈溢出。调用函数时，将框架对象压入调用堆栈，并在函数返回时从调用堆栈弹出。框架对象包含信息，例如局部变量和函数返回时返回的代码行。

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

但是，如果递归函数做的最后一件事是进行递归调用并返回其返回值，则没有理由需要将当前帧对象保留在调用堆栈中。毕竟，如果在递归函数调用之后没有任何代码，则没有理由继续使用当前帧对象的局部变量。因此，我们可以立即摆脱当前框架对象，而不必将其保留在调用堆栈中。这样的最终结果是您的调用堆栈不会增加大小，因此不会导致堆栈溢出。

编译器或解释器必须具有尾调用优化功能，才能识别何时可以应用尾调用优化。即使这样，您也可能已经在递归函数中重新安排了代码以利用尾部调用优化，如果这种潜在的可读性下降值得优化，则取决于您。