0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
（图片来源网络，侵删）
下面我将为你展示几种不同的 Java 实现方法,并分析它们的优缺点。
递归实现
这是最直观、最容易理解的方法,因为它直接翻译了数学定义。
public class Fibonacci {
/**
* 使用递归计算斐波那契数列的第 n 项
* @param n 要计算的项数（从 0 开始）
* @return 第 n 项的值
*/
public static long fibonacciRecursive(int n) {
// 基本情况：第0项是0，第1项是1
if (n <= 1) {
return n;
}
// 递归情况：第n项 = 第n-1项 + 第n-2项
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
public static void main(String[] args) {
int n = 10;
System.out.println("使用递归方法计算第 " + n + " 项斐波那契数:");
// 注意：对于较大的n，递归方法会非常慢，甚至导致栈溢出
System.out.println("fib(" + n + ") = " + fibonacciRecursive(n));
}
}
优点:
- 代码简洁易懂：逻辑与数学定义完全一致,可读性非常高。
缺点:
（图片来源网络，侵删）
- 性能极差：存在大量的重复计算，计算
fib(5)时，fib(3)会被计算两次，fib(2)会被计算三次，时间复杂度是指数级的 O(2^n)。 - 栈溢出风险：每次递归调用都会在调用栈上添加一个新的栈帧，当
n很大时（例如超过 40），调用栈会变得非常深，最终导致StackOverflowError。
迭代实现（推荐）
这是在实际开发中最常用、最高效的方法，它通过循环和变量来保存中间结果,避免了重复计算。
public class Fibonacci {
/**
* 使用迭代（循环）计算斐波那契数列的第 n 项
* @param n 要计算的项数（从 0 开始）
* @return 第 n 项的值
*/
public static long fibonacciIterative(int n) {
// 处理 n=0 和 n=1 的情况
if (n <= 1) {
return n;
}
long a = 0; // 代表第 n-2 项
long b = 1; // 代表第 n-1 项
long c; // 代表当前项
// 从第 2 项开始循环，直到第 n 项
for (int i = 2; i <= n; i++) {
c = a + b; // 计算当前项
a = b; // 更新 a 为前一项的值
b = c; // 更新 b 为当前项的值
}
return b;
}
public static void main(String[] args) {
int n = 50;
System.out.println("使用迭代方法计算第 " + n + " 项斐波那契数:");
// 迭代方法可以非常快速地计算出大数
System.out.println("fib(" + n + ") = " + fibonacciIterative(n));
}
}
优点:
- 性能极高：时间复杂度是线性的 O(n),只进行一次循环。
- 不会栈溢出：不使用递归，不会增加调用栈的深度，可以安全地计算非常大的
n（只要结果不超过long类型的范围）。
缺点:
- 可读性稍差：相比递归，需要理解变量
a,b,c是如何代表数列中前后项的。
使用动态规划（带备忘录的递归）
这种方法结合了递归的清晰性和迭代的效率，它用一个数组（或哈希表）来存储已经计算过的结果,避免重复计算。
（图片来源网络，侵删）
import java.util.Arrays;
public class Fibonacci {
// 使用一个数组作为“备忘录”
private static long[] memo;
/**
* 使用带备忘录的递归（动态规划）计算斐波那契数列的第 n 项
* @param n 要计算的项数（从 0 开始）
* @return 第 n 项的值
*/
public static long fibonacciMemoized(int n) {
memo = new long[n + 1]; // 创建备忘录数组
Arrays.fill(memo, -1); // 初始化为 -1，表示未计算
memo[0] = 0;
if (n > 0) {
memo[1] = 1;
}
return helper(n);
}
private static long helper(int n) {
// 如果备忘录中已经有值，直接返回，避免重复计算
if (memo[n] != -1) {
return memo[n];
}
// 否则，进行计算并存入备忘录
memo[n] = helper(n - 1) + helper(n - 2);
return memo[n];
}
public static void main(String[] args) {
int n = 50;
System.out.println("使用带备忘录的递归方法计算第 " + n + " 项斐波那契数:");
System.out.println("fib(" + n + ") = " + fibonacciMemoized(n));
}
}
优点:
- 性能高：时间复杂度也是 O(n),每个值只计算一次。
- 保留递归结构：代码结构上更接近递归,对于某些问题比纯迭代更易于实现。
缺点:
- 空间复杂度高：需要一个额外的数组来存储备忘录，空间复杂度为 O(n)。
- 有递归的局限性：虽然避免了指数级的重复计算，但调用栈深度仍然是 O(n)，对于极大的
n仍有栈溢出的风险（比纯递归好很多，但不如迭代稳健）。
使用 Stream API (Java 8+)
这是一种非常现代和函数式的实现方式,代码非常简洁。
import java.util.stream.Stream;
public class Fibonacci {
/**
* 使用 Java 8 Stream API 生成斐波那契数列
* @param n 要计算的项数（从 0 开始）
* @return 第 n 项的值
*/
public static long fibonacciStream(int n) {
if (n < 0) {
throw new IllegalArgumentException("n must be non-negative");
}
// 使用 iterate 生成无限流，然后截取前 n+1 项，最后获取第 n 项
return Stream.iterate(new long[]{0, 1}, fib -> new long[]{fib[1], fib[0] + fib[1]})
.limit(n + 1)
.map(fib -> fib[0])
.reduce((a, b) -> b) // 或者 .skip(n).findFirst().get()
.orElse(0L);
}
public static void main(String[] args) {
int n = 10;
System.out.println("使用 Stream API 计算第 " + n + " 项斐波那契数:");
System.out.println("fib(" + n + ") = " + fibonacciStream(n));
}
}
优点:
- 代码优雅、函数式：非常适合喜欢函数式编程风格的人。
- 性能好：底层实现仍然是高效的迭代。
缺点:
- 可读性可能较低：对于不熟悉 Stream API 的开发者来说,代码可能难以理解。
总结与建议
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 | 推荐场景 |
|---|---|---|---|---|---|
| 递归 | O(2^n) | O(n) | 代码直观易懂 | 性能极差，易栈溢出 | 学术学习，理解递归概念 |
| 迭代 | O(n) | O(1) | 性能最高，最稳健 | 代码稍显冗长 | 生产环境，绝大多数情况下的首选 |
| 动态规划 | O(n) | O(n) | 结合递归清晰性和高性能 | 空间开销大，仍有栈溢出风险 | 复杂动态规划问题，需要递归结构 |
| Stream API | O(n) | O(n) | 代码优雅，函数式 | 可读性因人而异 | 现代Java项目，展示函数式编程能力 |
最终建议：
- 如果你是初学者，先理解递归的原理，然后一定要掌握迭代方法。
- 在实际项目或面试中，迭代方法是最佳选择,因为它是最优的解决方案。
- 如果你使用的是 Java 8 或更高版本，并且喜欢函数式编程风格，Stream API 是一个展示现代 Java 技巧的好方法。
