尾递归调用（C入门加书本例子）

Question

在C Primer Plus (6th edition), it defines the tail recursion concept 以这种方式：

In the simplest form of recursion, the recursive call is at the end of the function, just before the return statement. This is called tail recursion, or end recursion, because the recursive call comes at the end. Tail recursion is the simplest form because it acts like a loop.

并给出了尾递归计算阶乘的例子：

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

它还做了一个旁注，我认为这是不正确的：

Note that although the recursive call to rfact() is not the last line in the function, it is the last statement executed when n > 0, so it is tail recursion.

可以清楚地看到最后一条语句是n * rfact(n - 1)，如果递归展开，会导致一连串的延迟乘法。该过程本质上是递归的，因此实现不能像 here.

中描述的那样是尾递归的

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

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

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

Answer 2

给定的定义和示例都具有误导性。 tail recursion的定义是：

A function call is said to be tail recursive if there is nothing to do after the function returns except return its value.

递归调用不一定要在函数的return语句或最后一个语句之前。看一个例子：

function foo(data) {
    a(data);
    return b(data);
}

在这种情况下，a 就在 return 语句之前，但 b 位于尾部位置。

function bar(data) {
    if ( a(data) ) {
        return b(data);
    }
    return c(data);
}

在这个例子中，b 和 c 都在尾部位置，尽管 b 不在函数 bar 的末尾。

在您给出的示例中，函数在 return 之前执行的最后一件事是乘法

ans = n * rfact(n - 1);

因此，它不是尾递归函数。

尾递归函数的例子是

factorial1(n, accumulator) {
    if (n == 0) return accumulator;
    return factorial1(n - 1, n * accumulator);  // The last thing, before return, performed 
                                                // by factorial1 is to call itself. 
  }

  factorial(n) {
    return factorial1(n, 1);
  }

可能会被编译器优化为

factorial1(n, accumulator) {
    while (n != 0) {
      accumulator *= n;
      n -= 1;
    }
    return accumulator;
  }

尾递归调用（C入门加书本例子）

Tail recursion call (C primer plus book example)

c

tail-recursion