尾递归究竟如何工作？
我几乎了解尾递归如何工作，以及它和正常递归之间的区别。 我只是不明白为什么它不需要堆栈来记住它的返回地址。
// 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;
}