当我开始学习口齿不清时,我遇到了“尾部递归”这个词。这到底是什么意思?
当前回答
简而言之,尾部递归将递归调用作为函数中的最后一条语句,这样就不必等待递归调用。
所以这是一个尾部递归,即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++——汇编视图”的长文
其他回答
尾部递归是函数调用的递归函数自身位于函数的末尾(“尾部”),其中没有计算在递归调用返回后完成。许多编译器优化以将递归调用更改为尾部递归调用或迭代调用。
考虑计算一个数的阶乘的问题。
一种简单的方法是:
factorial(n):
if n==0 then 1
else n*factorial(n-1)
假设你调用阶乘(4)。递归树为:
factorial(4)
/ \
4 factorial(3)
/ \
3 factorial(2)
/ \
2 factorial(1)
/ \
1 factorial(0)
\
1
上述情况下的最大递归深度为O(n)。
但是,请考虑以下示例:
factAux(m,n):
if n==0 then m;
else factAux(m*n,n-1);
factTail(n):
return factAux(1,n);
factTail(4)的递归树为:
factTail(4)
|
factAux(1,4)
|
factAux(4,3)
|
factAux(12,2)
|
factAux(24,1)
|
factAux(24,0)
|
24
这里,最大递归深度是O(n),但没有一个调用向堆栈添加任何额外变量。因此编译器可以取消堆栈。
尾部递归函数是一个递归函数,其中递归调用是函数中最后执行的事情。
常规递归函数,我们有堆栈,每次调用递归函数中的递归函数时,都会向调用堆栈添加另一层。在正常递归中空间: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);
}
}
在进行递归调用后,我们不需要记住任何内容
下面是一个使用尾部递归进行阶乘的常见Lisp示例。由于无堆栈的性质,人们可以进行疯狂的大型阶乘计算。。。
(defun ! (n &optional (product 1))
(if (zerop n) product
(! (1- n) (* product n))))
然后为了好玩,你可以尝试(格式化nil“~R”(!25))
重要的一点是尾部递归本质上等同于循环。这不仅仅是一个编译器优化的问题,而是一个关于表现力的基本事实。这是双向的:你可以采取任何形式的循环
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);
}
(用参数较少的函数“包装”尾部递归函数是一种常见的函数习惯用法。)
使用常规递归,每个递归调用将另一个条目推送到调用堆栈中。递归完成后,应用程序必须将每个条目向下弹出。
使用尾部递归,根据语言的不同,编译器可以将堆栈折叠为一个条目,这样可以节省堆栈空间。。。大型递归查询实际上会导致堆栈溢出。
基本上,尾部递归可以优化到迭代中。