我几乎理解尾递归是如何工作的以及它与正常递归之间的区别。我只是不明白为什么它不需要堆栈来记住它的返回地址。
// 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);
}
在尾递归函数中调用函数本身后无事可做,但对我来说没有意义。
编译器只能转换它
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;
}
你问为什么“它不需要堆栈来记住它的返回地址”。
我想转过身来。它确实使用堆栈来记住返回地址。诀窍在于尾递归发生的函数在堆栈上有自己的返回地址,当它跳转到被调用函数时,它会将其视为自己的返回地址。
具体而言,没有尾调用优化:
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
的位置。
编辑:上面的例子使用一个函数调用另一个函数的情况。当函数调用自身时,机制是相同的。
尾递归通常可以由编译器转换为循环,尤其是在使用累加器时。
// 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;
}
常规递归函数中的返回值由两种类型的值组成:
我们来看看你的例子:
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 Recursion Optimization,也有更复杂的优化被称为Tail recursion modulo
递归函数是一个自己调用的函数
它允许程序员使用最少量的代码编写高效的程序。
缺点是如果写得不正确,它们会导致无限循环和其他意外结果。
我将解释Simple Recursive函数和Tail Recursive函数
为了编写一个简单的递归函数
从给定的例子:
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);
是否要进行实际处理
让我逐一打破任务,以便于理解。
如果我运行fact(4)
,让我们看看内部会发生什么
public static int fact(4){
if(4 <=1)
return 1;
else
return 4 * fact(4-1);
}
If
循环失败所以它转到else
循环所以它返回4 * fact(3)
4 * fact(3)
代入n = 3public static int fact(3){
if(3 <=1)
return 1;
else
return 3 * fact(3-1);
}
If
循环失败,所以它转到else
循环
所以它返回3 * fact(2)
记得我们称之为```4 * fact(3)``
fact(3) = 3 * fact(2)
的输出
到目前为止,堆栈有4 * fact(3) = 4 * 3 * fact(2)
4 * 3 * fact(2)
代入n = 2public static int fact(2){
if(2 <=1)
return 1;
else
return 2 * fact(2-1);
}
If
循环失败,所以它转到else
循环
所以它返回2 * fact(1)
记得我们叫4 * 3 * fact(2)
fact(2) = 2 * fact(1)
的输出
到目前为止,堆栈有4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)
4 * 3 * 2 * fact(1)
代入n = 1public static int fact(1){
if(1 <=1)
return 1;
else
return 1 * fact(1-1);
}
If
循环是真的
所以它返回1
记得我们叫4 * 3 * 2 * fact(1)
fact(1) = 1
的输出
到目前为止,堆栈有4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1
最后,事实(4)= 4 * 3 * 2 * 1 = 24的结果
Tail Recursion会是
public static int fact(x, running_total=1) {
if (x==1) {
return running_total;
} else {
return fact(x-1, running_total*x);
}
}
public static int fact(4, running_total=1) {
if (x==1) {
return running_total;
} else {
return fact(4-1, running_total*4);
}
}
If
循环失败所以它转到else
循环所以它返回fact(3, 4)
fact(3, 4)
代入n = 3public static int fact(3, running_total=4) {
if (x==1) {
return running_total;
} else {
return fact(3-1, 4*3);
}
}
If
循环失败,所以它转到else
循环
所以它返回fact(2, 12)
fact(2, 12)
代入n = 2public static int fact(2, running_total=12) {
if (x==1) {
return running_total;
} else {
return fact(2-1, 12*2);
}
}
If
循环失败,所以它转到else
循环
所以它返回fact(1, 24)
fact(1, 24)
代入n = 1public static int fact(1, running_total=24) {
if (x==1) {
return running_total;
} else {
return fact(1-1, 24*1);
}
}
If
循环是真的
所以它返回running_total
running_total = 24
的输出
最后,事实(4,1)= 24的结果
我的回答更多的是猜测,因为递归与内部实现有关。
在尾递归中,递归函数在同一函数的末尾被调用。可能编译器可以通过以下方式进行优化:
正如您所看到的,我们在相同函数的下一次迭代之前清理原始函数,因此我们实际上并没有“使用”堆栈。
但我相信如果在函数内部调用析构函数,那么这种优化可能不适用。
编译器足以理解尾递归。如果从递归调用返回,则没有挂起操作,递归调用是最后一个语句,属于尾递归类别。编译器基本上执行尾递归优化,删除堆栈实现。考虑下面的代码。
void tail(int i) {
if(i<=0) return;
else {
system.out.print(i+"");
tail(i-1);
}
}
执行优化后,上面的代码将转换为下面的代码。
void tail(int i) {
blockToJump:{
if(i<=0) return;
else {
system.out.print(i+"");
i=i-1;
continue blockToJump; //jump to the bolckToJump
}
}
}
这就是编译器执行Tail Recursion Optimization的方法。