代码之家 › 专栏 › 技术社区 › Alex

尾部递归调用(C primer加上书本示例)

tail-recursion c

Alex · 技术社区 · 10 年前

在 C Primer Plus (6th edition) ,它定义了 tail recursion concept 以这种方式:

在最简单的递归形式中,递归调用位于函数的末尾,就在返回语句之前。这被称为尾部递归或结束递归,因为递归调用在结束时进行。尾部递归是最简单的形式,因为它就像一个循环。

它给出了一个以尾部递归方式计算阶乘的例子:

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) 如果递归展开,将导致一系列延迟乘法。该过程本质上是递归的,因此实现不能像所描述的那样是尾部递归的 here .

这个例子有误导性。你的意见是什么?

2 回复 | 直到 10 年前

abligh 10 年前

就一本好的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”命令替换递归调用。仅当递归的值被直接返回时,才进行编译器修改。您会注意到,在您的示例中,情况并非如此。

haccks 10 年前

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

如果函数返回后除了返回其值之外没有任何事情可做,则函数调用被称为尾部递归。

递归调用不一定要在函数的返回语句或最后一个语句之前。请参见示例:

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 .

在给定的示例中,函数在返回之前执行的最后一件事是乘法

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