这是尾递归吗？

Question

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

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)

Answer 1

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

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

为了进行比较,这里是方法的尾递归实现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,并且更好地切换到迭代算法.