这个函数真的是尾递归吗？

Question

我在Programming Interviews Exposed(第3版)中阅读了有关递归的内容,其中它们呈现以下递归factorial函数:

int factorial(int n){
    if (n > 1) { /* Recursive case */
        return factorial(n-1) * n;
    } else {     /* Base case */
        return 1;
    }
}

在同一页面的底部(第108页),他们讨论了尾递归函数:

请注意,当递归调用返回的值本身立即返回时,如前面的定义所示factorial,该函数是尾递归的.

但这是真的吗？函数中的最后一个调用是*调用,因此不会保留此堆栈帧(如果我们不考虑编译器优化)？这真的是尾递归吗？

Answer 1

您可以将其重写为tail-recursive:

int factorial(int n){
    return factorial2(n, 1);
}
int factorial2(int n, int accum) {
    if (n < 1) {
       return accum;
    } else {
        return factorial2(n - 1, accum * n);
    }
}