斐波那契数列的算法思路和Java代码实现
斐波那契数列的算法思路和Java代码实现。
算法思路
斐波那契数列是一个非常经典的数列，在数学上以递推的方式定义为：
F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) (n >= 2)
根据这个递推关系式，我们可以用递归或者循环的方式来实现斐波那契数列。
递归法
递归法是最基本的实现方式。当 n = 0 或者 n = 1 时，斐波那契数列的第 n 个数就是 n。当 n >= 2 时，斐波那契数列的第 n 个数就是前两个数之和。因此，我们可以使用递归来实现斐波那契数列，递归过程中依次计算前两个数之和。
public int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
迭代法
迭代法是一种比较高效的实现方式。我们定义三个变量 a、b、c 表示斐波那契数列的前三个数，初始化时 a = 0，b = 1，c = 0。然后从第三个数开始用循环计算每个数的值，直到计算到第 n 个数为止。
public int fib(int n) {
if (n <= 1) {
return n;
}
int a = 0, b = 1, c = 0;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
这两种方法的时间复杂度和空间复杂度都不同，递归法时间复杂度较高，所以不推荐使用，迭代法时间复杂度较低，空间复杂度也较低，所以是最优的选择。
