当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?
当前回答
尾部递归函数是一个递归函数,其中递归调用是函数中最后执行的事情。
常规递归函数,我们有堆栈,每次调用递归函数中的递归函数时,都会向调用堆栈添加另一层。在正常递归中空间: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解释器不支持它。
如果每个递归情况仅由对函数本身的调用组成,并且可能具有不同的参数,则函数是尾部递归的。或者,尾部递归是没有待定工作的递归。注意,这是一个与编程语言无关的概念。
考虑定义如下的函数:
g(a, b, n) = a * b^n
一种可能的尾部递归公式是:
g(a, b, n) | n is zero = a
| n is odd = g(a*b, b, n-1)
| otherwise = g(a, b*b, n/2)
如果您检查g(…)的每一个涉及递归情况的RHS,您会发现整个RHS都是对g(……)的调用,仅此而已。这个定义是尾部递归的。
作为比较,非尾部递归公式可能是:
g'(a, b, n) = a * f(b, n)
f(b, n) | n is zero = 1
| n is odd = f(b, n-1) * b
| otherwise = f(b, n/2) ^ 2
f(…)中的每个递归情况都有一些需要在递归调用之后进行的未决工作。
注意,当我们从“g”到“g”时,我们充分利用了关联性(和交换性)乘法。这并不是偶然的,在大多数需要将递归转换为尾递归的情况下,都会利用这些财产:如果我们想急切地做一些工作,而不是让它等待,我们必须使用关联性之类的东西来证明答案是一样的。
尾部递归调用可以通过向后跳转来实现,而不是使用堆栈进行常规递归调用。注意,检测尾部呼叫或发出向后跳转通常很简单。然而,通常很难重新排列参数,以便向后跳转。由于此优化不是免费的,语言实现可以选择不实现此优化,或者通过使用“tailcall”指令标记递归调用和/或选择更高的优化设置来要求选择加入。
然而,某些语言(例如Scheme)确实需要所有实现来优化尾部递归函数,甚至可能需要所有尾部位置的调用。
在大多数命令式语言中,向后跳转通常被抽象为(while)循环,而尾部递归在优化为向后跳转时,与循环同构。
使用常规递归,每个递归调用将另一个条目推送到调用堆栈中。递归完成后,应用程序必须将每个条目向下弹出。
使用尾部递归,根据语言的不同,编译器可以将堆栈折叠为一个条目,这样可以节省堆栈空间。。。大型递归查询实际上会导致堆栈溢出。
基本上,尾部递归可以优化到迭代中。
重要的一点是尾部递归本质上等同于循环。这不仅仅是一个编译器优化的问题,而是一个关于表现力的基本事实。这是双向的:你可以采取任何形式的循环
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);
}
(用参数较少的函数“包装”尾部递归函数是一种常见的函数习惯用法。)