Ala*_*ano 120 c algorithm recursion tail-recursion
我几乎理解尾递归是如何工作的以及它与正常递归之间的区别.我只是不明白为什么它不要求堆栈来记住它的返回地址.
// tail recursion
int fac_times (int n, int acc) {
if (n == 0) return acc;
else return fac_times(n - 1, acc * n);
}
int factorial (int n) {
return fac_times (n, 1);
}
// normal recursion
int factorial (int n) {
if (n == 0) return 1;
else return n * factorial(n - 1);
}
在尾递归函数中调用函数本身后无事可做,但对我来说没有意义.
Ale*_*nze 166
编译器只能转换它
int fac_times (int n, int acc) {
if (n == 0) return acc;
else return fac_times(n - 1, acc * n);
}
进入这样的事情:
int fac_times (int n, int acc) {
label:
if (n == 0) return acc;
acc *= n--;
goto label;
}
Lin*_*cer 56
你问为什么"它不需要堆栈来记住它的返回地址".
我想转过身来.它确实使用堆栈来记住返回地址.诀窍在于尾递归发生的函数在堆栈上有自己的返回地址,当它跳转到被调用函数时,它会将其视为自己的返回地址.
具体而言,没有尾调用优化:
f: ...
CALL g
RET
g:
...
RET
在这种情况下,当g调用时,堆栈将如下所示:
SP -> Return address of "g"
Return address of "f"
另一方面,尾部调用优化:
f: ...
JUMP g
g:
...
RET
在这种情况下,当g调用时,堆栈将如下所示:
SP -> Return address of "f"
很明显,当g返回时,它将返回到f被调用的位置.
编辑:上面的例子使用一个函数调用另一个函数的情况.当函数调用自身时,机制是相同的.
mep*_*ell 11
尾递归通常可以由编译器转换为循环,尤其是在使用累加器时.
// tail recursion
int fac_times (int n, int acc = 1) {
if (n == 0) return acc;
else return fac_times(n - 1, acc * n);
}
会编译成类似的东西
// accumulator
int fac_times (int n) {
int acc = 1;
while (n > 0) {
acc *= n;
n -= 1;
}
return acc;
}
Luc*_*iro 11
常规递归函数中的返回值由两种类型的值组成:
我们来看看你的例子:
int factorial (int n) {
if (n == 0) return 1;
else return n * factorial(n - 1);
}
例如,帧f(5)"存储"它自己的计算(5)的结果和f(4)的值.如果我调用factorial(5),就在堆栈调用开始崩溃之前,我有:
[Stack_f(5): return 5 * [Stack_f(4): 4 * [Stack_f(3): 3 * ... [1[1]]
请注意,除了我提到的值之外,每个堆栈还存储函数的整个范围.因此,递归函数f的内存使用是O(x),其中x是我必须进行的递归调用的数量.所以,如果我需要1kb的RAM来计算阶乘(1)或阶乘(2),我需要~100k来计算阶乘(100),依此类推.
在Tail Recursion中,我使用参数将每个递归帧中的部分计算结果传递给下一个递归帧.让我们看看我们的阶乘示例,Tail Recursive:
int factorial(int n){int helper(int num,int accumulation){if num == 0 return accumulation else return helper(num - 1,cumulative*num)} return helper(n,1)
}
让我们看看它在factorial(4)中的帧:
[Stack f(4, 5): Stack f(3, 20): [Stack f(2,60): [Stack f(1, 120): 120]]]]
看到差异？在"常规"递归调用中,返回函数以递归方式组成最终值.在Tail Recursion中,它们仅引用基本案例(最后一个评估).我们将accumulator称为跟踪旧值的参数.
常规递归函数如下:
type regular(n)
base_case
computation
return (result of computation) combined with (regular(n towards base case))
要在Tail递归中转换它,我们:
看:
type tail(n):
type helper(n, accumulator):
if n == base case
return accumulator
computation
accumulator = computation combined with accumulator
return helper(n towards base case, accumulator)
helper(n, base case)
看到不同？
由于没有状态存储在Tail Call堆栈的非边界案例中,因此它们并不那么重要.然后,一些语言/解释器将旧堆栈替换为新堆栈.因此,在没有堆栈帧限制调用次数的情况下,Tail Calls在这些情况下的行为就像for循环一样.
由编译器来优化它,或者不是.
这是一个简单的例子,展示了递归函数的工作原理:
long f (long n)
{
if (n == 0) // have we reached the bottom of the ocean ?
return 0;
// code executed in the descendence
return f(n-1) + 1; // recurrence
// code executed in the ascendence
}
尾递归是一个简单的递归函数,其中重复在函数结束时完成,因此没有代码在ascendence中完成,这有助于大多数高级编程语言的编译器执行所谓的尾递归优化,也有一个更复杂的优化称为Tail递归模