这是尾递归吗？

Question

这是尾递归吗？

javarecursioncomputer-sciencefibonaccitail-recursion

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)

- BluceRee

2个回答

4

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

人们之所以关心一个调用是否是尾调用，是因为有一种优化方法可以将尾调用替换为分支语句，从而避免需要创建新的堆栈帧。这可以在有限的堆栈上进行无限的尾递归。

然而，由于你使用了java标签，你应该知道当前的Java实现并没有实现尾调用优化。在Java中深度递归的方法调用可能会导致StackOverflowError。

- Stephen C

我认为IBM JDK/JRE（不记得名字了）曾经优化过尾调用。 - Javier

这很有趣。我想知道他们是如何绕过安全相关问题的，以便在Sun / Oracle / OpenJDK代码库中实现它... - Stephen C

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Óscar López · Accepted Answer

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

在您的代码中，在两个递归调用结束之后，还有一个加法操作需要执行。因此，该方法是递归的，但不是尾递归的。

为了比较，这里是一个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 ，最好切换到迭代算法。