Java递归斐波那契函数有什么问题？

Question

我刚刚写了这篇文章，但是由于某些原因，在控制台中，我得到了一些看起来正确但顺序错误的数字，有些数字是重复的。有什么问题吗？

public class Fibonacci {
    public static void main(String[] args) {
        int n = 5;

        fibonacci(n);
    }

    public static int fibonacci(int n) {
        if(n == 0) {
            System.out.println(0);
            return 0;
        } else if(n == 1) {
            System.out.println(1);
            return 1;
        } else {
            int result = fibonacci(n - 1) + fibonacci(n - 2);
            System.out.println(result);
            return result;
        }
    }
}

Answer 1

您的程序正确计算了斐波那契数。这是在fibonacci的顶级调用中打印的最后一个数字。

某些数字被重复打印，因为它们被多次计算。 fibonacci(5)调用fibonacci(4) + fibonacci(3)，后者调用fibonacci(3) + fibonacci(2) + fibonacci(2) + fibonacci(1)，并且我们已经有两个单独的具有相同参数的递归调用。随着递归调用的进一步下降，重复调用将更多。

对于较低的输入，例如5，这是可以的，但是对于较大的数字，您将遇到性能问题，因为此算法本质上是指数的。复杂度为O（2 ⁿ

）。您当前的打印语句突出显示了正在执行的所有其他计算。您可以删除它们，但是算法的复杂度仍然是指数级的。

即使您的程序当前是正确的，也可以通过将对fibonacci的中间调用的结果存储在数组中来消除指数复杂度，而用线性复杂度（O（n））代替。这样，每个中间步骤仅计算一次。

Answer 2

[如果您想查看斐波那契数列直到设置的项，请从fibonacci(int n)方法中删除所有输出，而在主行中只有一个print方法处于从1到您的for循环中设定期限。

Answer 3

我建议您删除这些打印声明。他们使您感到困惑。

Answer 4

由于您的函数是递归的，所以每个斐波那契数均打印多个。如果您不想这样做，请将打印移到功能之外

Answer 5

您的方法非常好，多余的打印内容来自对fibonacci方法的递归调用。 fib的4调用堆栈为：

Answer 6

有人可以告诉我，我怎么可以这样练习。很简单，但是我只是一个初学者。实践去：想象一下，某些事物与斐波达契数呈线性关系。要用int值“ s”来命名。我的意思是在实践中（抱歉，我的英语不好）：s1-> 0，s2-> 1，s3-> 1，s4-> 2，依此类推。那么我怎样才能打印出与整数值S一起表示的Fibodacci序列号呢？我只需要一个印刷的斐波达契编号。我希望有人能尽快帮助我，因为我自己不能做到。