尾递归调用(C primer plus book example)

Question

在C Primer Plus(第6版)中,它 以这种方式定义尾递归概念:

在最简单的递归形式中,递归调用位于函数的末尾,就在return语句之前.这称为尾递归或结束递归,因为递归调用最后会发生.尾递归是最简单的形式,因为它就像一个循环.

它给出了以尾递归方式计算阶乘的示例:

long rfact(int n) {
    long ans;
    if (n > 0)
        ans = n * rfact(n - 1);
    else
        ans = 1;
    return ans;
 }

它也是一个侧面说明,在我看来这是不正确的:

请注意,虽然对rfact()的递归调用不是函数中的最后一行,但它是n> 0时执行的最后一个语句,因此它是尾递归.

可以清楚地看到,最后一个语句是n * rfact(n - 1),如果递归扩展,它将导致一系列延迟乘法.该过程在本质上是递归的,从而所描述的实现不能尾递归这里.

这个例子具有误导性.你有什么意见？

Answer 1

就一本优秀的 C 编程书籍而言，我使用的是 C 编程语言。

你说这不是尾递归是正确的。阶乘的典型尾递归示例是：

int factorial(int x) {
    return tailfactorial(x, 1);
}

int tailfactorial(int x, int multiplier) {
    if (x <= 0) {
        return multiplier;    
    }    
    return tailfactorial(x - 1, x * multiplier);
}

我想你的书没有解释尾递归的目的。使用尾递归是为了不增加“堆栈深度”。编译器可以用“goto”命令替换递归调用，这不会增加堆栈深度。仅当直接返回递归值时才会进行此编译器修改。您会在示例中注意到情况并非如此。