Fibonacci序列如何工作[重复]

Question

这个问题在这里已有答案：

• Java recursive Fibonacci sequence 35个答案

我很困惑Java如何运行这个特定的代码。我对Fibonacci序列很满意，但对于如何解决这个特定方法的运行方式并不完全正确。很明显，如果n为0，我将返回0，如果n为1，则返回1.现在让我们说n为n传递3。我们返回fib（2）+ fib（1）。如果它首先从未计算过，它如何知道fib（2）是什么？它是否会再次通过整个函数来找出fib（2）是什么？什么时候停止？我的思绪会爆炸。

 public static int fib(int n){
    if (n == 0){
        return 0;
    }
    else if (n == 1){
        return 1;
    }
    return (fib(n-1) + fib(n-2));

}

Answer 1

您正在编写一个名为Recursion的编程/数学中最酷的概念之一。它可以是美丽的，但它也可以是一个诅咒。在学习递归函数的开始，我也被这些编译的自我调用怪物驱使，但过了一段时间我才意识到有多少问题可以通过递归更容易解决。所以回到你的问题。

所以根据维基百科的说法，Fibonacci序列是

“Fibonacci数的序列Fn由递归关系定义：

F n = F n−1 + F n−2

n是当前的数字。

所以在开始时我们称之为例子

fib(3);

在它调用的方法中

fib(2);

然后在fib（2）中调用

fib(1)

这返回1（因为if）所以这得到fib（2）和fib 2调用fib（0）导致0所以fib（2）返回1

因为fib（3）被其他方法打断，它仍然在返回点。目前看起来像那样。

return 1 + fib(3 - 2)

fib（1）返回1

最后，fib返回2

这有点难以解释，但我想你很快就能理解。

提示：当您无法理解某些内容执行时如何使用调试器。它可以帮助您实现数据和算法的可视化。它可以帮助您更快地理解。 FIB（1）