这是尾递归吗？ [英] Is this tail recursion?

问题描述

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

I have tried to find examples of tail recursion and I really don't see the difference between regular and tail. If this isn't tail recursion, can someone tell me why its not?

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 事情。

No, the method in the question does not use a tail recursion. A tail recursion is easily recognizable: the recursive step is the last thing that happens in the method.

在您的代码中，之后两个递归调用都结束了，还有一个操作要做-一个加法。因此该方法是 recursive ，而不是 tail-recursive 。

In your code, after both recursive calls end, there's one more operation to do - an addition. So the method is recursive, but not tail-recursive.

出于比较目的，这是一个尾递归 fib（）方法的实现-请注意我们如何传递额外的参数来保存递归状态，更重要的是，请注意，尚无任何操作要做递归调用返回后。

For comparison purposes, here's a tail-recursive implementation of the fib() method - notice how we need to pass extra parameters to save the state of the recursion, and more importantly, notice that there are no operations left to do after the recursive call returns.

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 ，并更好地切换到迭代算法。

The previous implementation will work fine up to n=92, for bigger numbers you'll have to use BigInteger instead of long, and better switch to an iterative algorithm.

这篇关于这是尾递归吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！