学习Java-不完全了解此序列的计算方式(Fibonacci) [英] Learning Java - Do not fully understand how this sequence is calculated (Fibonacci)

问题描述

我正在学习Java，我从互联网上获得了这段代码，并在Eclipse中运行它:

I am learning Java and I have this code from the internet and running it in Eclipse:

public class Fibonacci {

    public static void main (String [] args) { 
        for (int counter = 0; counter <= 3; counter++){
            System.out.printf("Fibonacci of %d is: %d\n",  counter, fibonacci(counter));

    }

    public static long fibonacci(long number) {
        if ((number == 0) || (number == 1))
             return number;
        else
             return fibonacci(number - 1) + fibonacci(number - 2);
    }
}

我试图理解它，但无法理解.因此，我遍历了代码，并通过 fibonacci 方法传递了 counter .由于计数器从 0 开始，这是首先传递的内容，然后是 1 ，我知道该方法将传递回 0 然后是 1.

I've tried to understand it but cannot get it. So I run through the code and counter gets passed in through the fibonacci method. As counter starts at 0 and this is what gets passed first, then 1 and I understand the method passes back 0 and then 1.

当到达2:时，它将返回 2-1 + 2-2 = 2 ，并且确实会返回此代码.
到达3:时，它将返回 3-1 + 3-2 = 3 ，但不会返回 3 ，而是返回 2.

When it reaches 2: it will return 2-1 + 2-2 = 2 and it does return this.
When it reaches 3: it will return 3-1 + 3-2 = 3 but it does not return 3 it returns 2.

请有人可以向我解释为什么我无法弄清楚这一点吗?

Please can someone explain to me why as I cannot figure this out?

谢谢

推荐答案

首先，我必须告诉您，此递归版本的费用很高，指数.了解了它的工作原理后，对您的建议是了解尾部递归性，编写一个 tail-recursive 解决方案，一个迭代解决方案，并将其与您当前的解决方案进行比较高值数字"的方法.

First, I have to tell you that this recursive version has a dramatic exponential cost. Once you understand how it works, my advice for you would be to learn about tail recursivity, write a tail-recursive solution, an iterative solution, and compare them to your current method for high values of "number".

然后，您的函数基本上使用斐波那契数列的数学定义:

Then, your function basically uses the mathematical definition of the Fibonacci sequence :

f0 = 1，f1 = 1，fn = fn-1 + fn-2对于所有n> = 2

例如，如果我们调用fibonacci(3)，则将返回fibonacci(2)+ fibonacci(1).首先将执行fibonacci(2)，并将返回fibonacci(1)+ fibonnacci(0).然后fibonacci(1)将立即返回1，因为它是一个终止情况.与fibonnacci(0)发生相同的事情，因此现在我们计算出fibonnacci(2)= 1 + 0 =1.让我们回到fibonacci(3)，它在这一点上已经部分评估:1 + fibonnacci(1).我们只需要计算fibonnacci(1)，我们最终可以返回1 +1 = 2.

For example if we call fibonacci(3), this will return fibonacci(2) + fibonacci(1). fibonacci(2) will be executed first and will return fibonacci(1) + fibonnacci(0). Then fibonacci(1) will return immediately 1 since it is a terminal case. It happens the same thing with fibonnacci(0), so now we have computed fibonnacci(2) = 1 + 0 = 1. Let's go back to fibonacci(3) which has been partially evaluated at this point : 1 + fibonnacci(1). We just have to compute fibonnacci(1) and we can finally return 1 + 1 = 2.

即使在这个小例子中，您也可以看到我们对fibonacci(1)进行了两次评估，这就是为什么该版本是如此之慢，它多次计算相同序列值的原因，并且当"number"为高.

Even in this little example, you can see that we evaluated twice fibonacci(1), that is why this version is so slow, it computes many times the same values of the sequence, and it gets worth when "number" is high.

这篇关于学习Java-不完全了解此序列的计算方式(Fibonacci)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！