递归函数是一个自己调用的函数

它允许程序员用最少的代码编写高效的程序。

缺点是，如果编写不当，它们可能会导致无限循环和其他意外结果。

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

为了编写简单的递归函数

首先要考虑的一点是你应该什么时候决定出来是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);

是否要进行实际处理

为了便于理解，让我逐一完成任务。

让我们看看如果我运行事实（4），内部会发生什么

替换n=4

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

如果循环失败，则转到else循环因此它返回4*事实（3）

在堆栈内存中，我们有4*事实（3）替换n=3

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

如果循环失败，则转到else循环

因此它返回3*事实（2）

记住我们称之为“4*事实”（3）``

事实（3）的输出=3*事实（2）

到目前为止，堆栈具有4*事实（3）=4*3*事实（2）

在堆栈内存中，我们有4*3*事实（2）替换n=2

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

如果循环失败，则转到else循环

因此它返回2*事实（1）

记住我们称之为4*3*事实（2）

事实（2）的输出=2*事实（1）

到目前为止，堆栈具有4*3*事实（2）=4*3*2*事实（1）

在堆栈内存中，我们有4*3*2*事实（1）替换n=1

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

如果循环为真

所以它返回1

记住我们称之为4*3*2*事实（1）

事实（1）的输出=1

到目前为止，堆栈具有4*3*2*事实（1）=4*3*2*1

最后，事实（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);
    }
}

如果循环失败，则转到else循环因此它返回事实（3，4）

在堆栈内存中，我们有事实（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);
    }
}

如果循环失败，则转到else循环

因此它返回事实（2，12）

在堆栈内存中，我们有事实（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);
    }
}

如果循环失败，则转到else循环

因此它返回事实（1，24）

在堆栈内存中，我们有事实（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);
    }
}

如果循环为真

因此它返回running_total

running_total=24的输出

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

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

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);
}

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

术语文件对尾部递归的定义有这样的说法：

尾部递归/n/

如果您还没有厌倦它，请参阅尾部递归。

简而言之，尾部递归将递归调用作为函数中的最后一条语句，这样就不必等待递归调用。

所以这是一个尾部递归，即N（x-1，p*x）是函数中的最后一个语句，编译器聪明地发现它可以优化为for循环（阶乘）。第二个参数p携带中间乘积值。

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

这是编写上述阶乘函数的非尾部递归方式（尽管某些C++编译器可能无论如何都能优化它）。

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

但这不是：

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

我确实写了一篇题为“理解尾部递归——Visual Studio C++——汇编视图”的长文

在传统递归中，典型的模型是首先执行递归调用，然后获取递归调用的返回值并计算结果。通过这种方式，在每次递归调用返回之前，您不会得到计算结果。

在尾部递归中，首先执行计算，然后执行递归调用，将当前步骤的结果传递给下一个递归步骤。这导致最后一条语句的形式为（return（递归函数参数））。基本上，任何给定递归步骤的返回值都与下一个递归调用的返回值相同。

这样做的结果是，一旦准备好执行下一个递归步骤，就不再需要当前堆栈帧。这允许进行一些优化。事实上，使用一个适当编写的编译器，您永远不应该有带有尾部递归调用的堆栈溢出窃笑。只需在下一个递归步骤中重用当前堆栈帧。我很确定Lisp会这么做。

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