尾递归到底是如何工作的？

Question

我几乎理解了尾递归是如何工作的，以及它与普通递归之间的区别。我只是不明白为什么它不要求堆栈记住它的返回地址。

// 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);
}

在尾递归函数中调用函数本身后没有什么可做的，但对我来说这没有意义。

Answer 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;
}