当我开始学习口齿不清时，我遇到了“尾部递归”这个词。这到底是什么意思？
当前回答
尾部递归函数是一个递归函数，其中递归调用是函数中最后执行的事情。
常规递归函数，我们有堆栈，每次调用递归函数中的递归函数时，都会向调用堆栈添加另一层。在正常递归中空间：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);
}
}
在进行递归调用后，我们不需要记住任何内容
其他回答
递归函数是一个自己调用的函数
它允许程序员用最少的代码编写高效的程序。
缺点是，如果编写不当，它们可能会导致无限循环和其他意外结果。
我将解释简单递归函数和尾部递归函数
为了编写简单的递归函数
首先要考虑的一点是你应该什么时候决定出来是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
这本摘自《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）。如果输入的数字很高，可能会导致堆栈溢出。
尾部递归函数是一个递归函数，其中递归调用是函数中最后执行的事情。
常规递归函数，我们有堆栈，每次调用递归函数中的递归函数时，都会向调用堆栈添加另一层。在正常递归中空间：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);
}
}
在进行递归调用后，我们不需要记住任何内容
考虑一个将前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解释器不支持它。
这个问题有很多很好的答案。。。但我忍不住提出了另一种看法，即如何定义“尾部递归”，或者至少是“正确的尾部递归”。即：是否应该将其视为程序中特定表达式的属性？还是应该将其视为编程语言实现的属性？
关于后一种观点，Will Clinger的一篇经典论文“正确的尾部递归和空间效率”（PLDI 1998）将“正确的尾递归”定义为编程语言实现的属性。该定义被构造为允许忽略实现细节（例如调用堆栈实际上是通过运行时堆栈还是通过堆分配的帧链接列表表示的）。
为了实现这一点，它使用了渐近分析：不是人们通常看到的程序执行时间，而是程序空间使用情况。这样，堆分配的链接列表与运行时调用堆栈的空间使用最终是渐近等价的；因此，人们会忽略编程语言实现的细节（这一细节在实践中当然非常重要，但当试图确定给定的实现是否满足“属性尾部递归”的要求时，可能会让事情变得一团糟）
该论文值得仔细研究，原因如下：
它给出了程序尾部表达式和尾部调用的归纳定义。（这样的定义，以及为什么这样的电话很重要，似乎是这里给出的大多数其他答案的主题。）以下是这些定义，只是为了提供文本的味道：定义1以核心方案编写的程序的尾部表达式归纳如下。lambda表达式的主体是尾部表达式如果（如果E0 E1 E2）是尾部表达式，则E1和E2都是尾部表达式。其他的都不是尾部表达式。定义2尾部调用是作为过程调用的尾部表达式。
（尾部递归调用，或者正如论文所说，“self-tail调用”是尾部调用的一种特殊情况，其中过程本身被调用。）
它为评估核心方案的六个不同“机器”提供了正式定义，其中每个机器都具有相同的可观察行为，除了每个机器所处的渐近空间复杂性类。例如，在为分别为1。基于堆栈的内存管理，2。垃圾收集，但没有尾部调用。垃圾收集和尾部调用，本文继续介绍更高级的存储管理策略，如4。“evlis尾部递归”，在尾部调用的最后一个子表达式参数求值期间不需要保存环境，5。将闭包的环境减少到该闭包的自由变量，以及6。Appel和Shao定义的所谓“空间安全”语义。为了证明这些机器实际上属于六个不同的空间复杂性类，本文针对每对被比较的机器，提供了程序的具体示例，这些程序将揭示一台机器上的渐近空间爆炸，而不是另一台机器。
（现在仔细阅读我的答案，我不确定我是否真的抓住了克林格论文的关键点。但是，唉，我现在不能花更多的时间来研究这个答案。）
