4

我试图找到尾递归的例子，我真的看不出常规和尾之间的区别。如果这不是尾递归，有人可以告诉我为什么不是吗？

public static long fib(long index) {

// assume index >= 0

if (index == 0) // Base case

  return 0;

else

  if (index == 1) // Base case

    return 1;

  else

    // Reduction and recursive calls

    return fib(index - 1) + fib(index - 2);

}  // end of method fib(long index)
4

2 回答 2

16

不，问题中的方法不使用尾递归。尾递归很容易识别：递归步​​骤是方法中发生的最后一件事。

在您的代码中，在两个递归调用结束后，还有一个操作要做 - 加法。所以该方法是递归的，但不是尾递归的。

出于比较的目的，这里是该方法的尾递归实现fib()——注意我们需要传递额外的参数来保存递归的状态，更重要的是，请注意在递归调用返回后没有任何操作要做。

public static long fib(int n, long a, long b) {
    return n == 0 ? b : fib(n-1, a+b, a);
}

像这样使用它：

fib(10, 1, 0) // calculates the fibonacci of n=10
=> 55

之前的实现在 n=92 之前都可以正常工作，对于更大的数字，您必须使用BigInteger而不是long，并且更好地切换到迭代算法。

于 2013-09-03T00:19:47.657 回答
4

@Óscar López 已经回答了这个问题。

人们之所以有兴趣知道一个调用是否是尾调用，是因为有一个优化可以让一个尾调用替换为一个分支，从而避免了创建新堆栈帧的需要。这允许在有界堆栈上进行无界尾递归。

但是，由于您使用 标记了问题java，您应该知道当前的 Java 实现不实现尾调用优化。Java 中深度递归的方法调用可能会导致StackOverflowError.

于 2013-09-03T01:29:38.613 回答