当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?
当前回答
术语文件对尾部递归的定义有这样的说法:
尾部递归/n/
如果您还没有厌倦它,请参阅尾部递归。
其他回答
这是《计算机程序的结构和解释》中关于尾部递归的摘录。
在对比迭代和递归时,我们必须小心不要将递归过程的概念与递归过程。当我们将过程描述为递归时指过程定义所指的句法事实(直接或间接)到程序本身。但当我们将过程描述为遵循一种模式,即线性递归,我们谈论的是过程如何演变,而不是如何编写过程的语法。这似乎令人不安我们将递归过程(如事实iter)称为生成迭代过程。然而,这个过程实际上是迭代的:它的状态被其三个状态变量完全捕获解释器只需要跟踪三个变量执行该过程。过程和程序之间的区别可能是令人困惑的是,大多数通用语言的实现(包括Ada、Pascal和C) 以这样一种方式设计过程消耗的内存量会随着过程调用,迭代。因此,这些语言可以描述迭代仅通过使用专用的“循环构造”来处理例如do、repeat、until、for和while。实施方案不具有此缺陷。它将在恒定空间中执行迭代过程,即使迭代过程由递归过程描述。一具有此属性的实现称为尾部递归。用一个尾部递归实现,可以使用普通过程调用机制,使特殊迭代构造只作为句法糖有用。
我不是Lisp程序员,但我认为这会有所帮助。
基本上,这是一种编程风格,递归调用是最后一件事。
使用常规递归,每个递归调用将另一个条目推送到调用堆栈中。递归完成后,应用程序必须将每个条目向下弹出。
使用尾部递归,根据语言的不同,编译器可以将堆栈折叠为一个条目,这样可以节省堆栈空间。。。大型递归查询实际上会导致堆栈溢出。
基本上,尾部递归可以优化到迭代中。
尾部递归函数是一个递归函数,其中递归调用是函数中最后执行的事情。
常规递归函数,我们有堆栈,每次调用递归函数中的递归函数时,都会向调用堆栈添加另一层。在正常递归中空间: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);
}
}
在进行递归调用后,我们不需要记住任何内容
与普通递归相比,尾部递归非常快。它很快,因为祖先调用的输出不会写入堆栈以保持跟踪。但在正常递归中,所有祖先调用堆栈中的输出以保持跟踪。