1

I read about recursion in Programming Interviews Exposed (3rd ed.) where they present the following recursive factorial function:

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

On the bottom of the same page (page 108) they talk about tail-recursive functions:

Note that when the value returned by the recursive call is itself immediately returned, as in the preceding definition for factorial, the function is tail-recursive.

But is this really the case here? The last call in the function is the * call, so won't this stack frame be preserved (if we don't take compiler optimization into account)? Is this really tail-recursive?

4

4 回答 4

5

您可以将其重写为尾递归：

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);
    }
}
于 2013-04-20T01:51:22.237 回答
4

不，它不是尾递归的。返回的结果factorial(n-1)仍然必须乘以n，这需要factorial(n)重新获得控制权（因此要求调用factorial(n-1)是调用而不是跳转）。

话虽如此，即使它是尾递归的，编译器仍然可能不会对其进行 TCO。取决于编译器和您要求它执行的优化。

于 2013-04-20T01:45:26.170 回答
1

引用此链接：tail recursion using factorial as example

 factorial(n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
 }//equivalent to your code

 This definition is NOT tail-recursive since the recursive call to 
 factorial is not the last thing in the function 
 (its result has to be multiplied by n)
于 2013-04-20T01:45:48.357 回答
0

Tail Recursive是递归的一种特殊情况，其中函数的最后一个操作是递归调用。在尾递归函数中，从递归调用返回时没有待执行的操作。您提到的函数不是尾递归，因为有一个挂起的操作，即在递归调用返回时要执行乘法。如果你这样做：

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

将是一个尾递归函数。因为它在从递归调用返回时没有挂起的操作。

于 2013-04-20T01:57:11.027 回答