这是尾递归吗？

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

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)

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

在你的代码中，after两个递归调用都结束，还需要执行一项操作 - 加法。所以方法是递归的， 但不是尾递归.

出于比较目的，这里是尾递归实现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，并且更好地切换到迭代算法。