Java 实例 – 斐波那契数列（完整教程）

Java 实例 – 斐波那契数列：从零开始掌握递归与循环

在学习 Java 编程的道路上，斐波那契数列是一个绕不开的经典案例。它不仅出现在各大面试题库中，也是理解递归、循环和算法效率的绝佳切入点。如果你正在从零开始学 Java，或者想巩固基础算法思维，那么掌握这个例子，就等于为你的编程之路打下了一块坚实的基石。

斐波那契数列的定义很简单：从第 3 项开始，每一项都是前两项的和。数学表达式为：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)，当 n ≥ 2

比如：0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

这个数列看似简单，但它背后蕴含的算法思想却非常丰富。今天我们就通过多个角度，带你一步步实现 Java 实例 – 斐波那契数列，从最直观的递归方法，到高效的循环解法，再到记忆化优化，层层递进，帮助你真正吃透它。

递归实现：最直观，但最慢

递归是一种非常自然的表达方式，尤其适合处理具有“自相似”结构的问题。斐波那契数列就是一个典型的例子——计算 F(n) 就要先算 F(n-1) 和 F(n-2)，而它们又各自依赖更小的子问题。

下面是用 Java 实现的递归版本：

public static int fibonacciRecursive(int n) {
    // 基础情况：F(0) = 0，F(1) = 1
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    
    // 递归调用：F(n) = F(n-1) + F(n-2)
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

代码说明：

• 方法接收一个整数 n，表示要计算第 n 项。
• 当 n 为 0 或 1 时，直接返回对应值，这是递归的终止条件。
• 否则，递归调用自身两次，分别计算前两项并相加。

虽然代码简洁易懂，但它的性能非常差。因为每个函数调用都会产生两个新的调用，导致大量重复计算。比如计算 F(5) 时，F(3) 会被计算两次，F(2) 会被计算三次……时间复杂度高达 O(2^n)，实际运行时对 n > 40 的输入几乎无法完成。

💡 小贴士：递归就像一棵树，每一层都分叉，当 n 增大时，这棵树会迅速膨胀到不可承受的地步。

循环实现：效率大幅提升

既然递归太慢，我们换一种思路：用循环来“自底向上”地构建结果。这种方法只需要一次遍历，时间复杂度为 O(n)，空间复杂度 O(1)，是实际开发中最推荐的做法。

public static int fibonacciIterative(int n) {
    // 处理边界情况
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    
    // 初始化前两项
    int prev2 = 0;  // F(0)
    int prev1 = 1;  // F(1)
    int current = 0; // 将用于存储当前项
    
    // 从第 2 项开始循环计算到第 n 项
    for (int i = 2; i <= n; i++) {
        current = prev1 + prev2;  // F(i) = F(i-1) + F(i-2)
        prev2 = prev1;            // 更新前两项
        prev1 = current;
    }
    
    return current;
}

代码说明：

• 使用三个变量：prev2 保存 F(i-2)，prev1 保存 F(i-1)，current 用于计算当前值。
• 循环从 i = 2 开始，每次将前两项相加得到新项，并更新变量。
• 最终返回 current，即 F(n) 的值。

这个方法像“流水线”一样，一步步推进，每一步只依赖前两步的结果，避免了重复计算。如果你要计算第 100 项，它也能在毫秒内完成。

打印斐波那契数列前 N 项

除了计算单个值，我们还经常需要打印数列的前 N 项。这在数据可视化、算法测试中非常常见。

public static void printFibonacciSequence(int n) {
    System.out.println("斐波那契数列前 " + n + " 项：");
    
    for (int i = 0; i < n; i++) {
        System.out.print(fibonacciIterative(i) + " ");
    }
    System.out.println(); // 换行
}

调用示例：

printFibonacciSequence(10);

输出结果：

斐波那契数列前 10 项：
0 1 1 2 3 5 8 13 21 34 

这个方法结合了循环和迭代实现，清晰直观，适合初学者理解数列生成过程。

创建数组与初始化

在某些场景下，我们需要将整个数列存储在数组中，以便后续处理。比如统计某段区间内的奇数个数，或者用于图形绘制。

public static int[] generateFibonacciArray(int n) {
    // 创建长度为 n 的数组
    int[] fibArray = new int[n];
    
    // 初始化前两项
    if (n > 0) {
        fibArray[0] = 0;
    }
    if (n > 1) {
        fibArray[1] = 1;
    }
    
    // 从第 2 项开始，用循环填充数组
    for (int i = 2; i < n; i++) {
        fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
    }
    
    return fibArray;
}

调用示例：

int[] sequence = generateFibonacciArray(8);
for (int num : sequence) {
    System.out.print(num + " ");
}

输出结果：

0 1 1 2 3 5 8 13 

这个方法将结果集中存储，便于后续操作。例如你可以遍历数组判断哪些是质数，或者找出最大值等。

性能对比：递归 vs 循环

为了直观感受两种方法的差距，我们来做一个简单的性能测试。

public static void performanceTest() {
    int n = 35;
    
    // 测试递归方法
    long start = System.nanoTime();
    int result1 = fibonacciRecursive(n);
    long time1 = System.nanoTime() - start;
    
    // 测试循环方法
    start = System.nanoTime();
    int result2 = fibonacciIterative(n);
    long time2 = System.nanoTime() - start;
    
    System.out.println("计算 F(" + n + ") 的结果：");
    System.out.println("递归方法结果：" + result1 + "，耗时：" + time1 + " 纳秒");
    System.out.println("循环方法结果：" + result2 + "，耗时：" + time2 + " 纳秒");
}

输出示例（实际值可能略有差异）：

计算 F(35) 的结果：
递归方法结果：9227465，耗时：289000000 纳秒
循环方法结果：9227465，耗时：1500 纳秒

可以看到，循环方法快了上万倍！这就是为什么在实际项目中，我们总是优先选择非递归解法。

记忆化递归：折中方案

如果你坚持要用递归，又想避免重复计算，可以引入“记忆化”技术。简单来说，就是把已经算过的值存下来，下次直接查表。

import java.util.HashMap;

public static int fibonacciMemoized(int n, HashMap<Integer, Integer> memo) {
    // 如果已经计算过，直接返回缓存结果
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    
    // 基础情况
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    
    // 递归计算，并将结果存入缓存
    int result = fibonacciMemoized(n - 1, memo) + fibonacciMemoized(n - 2, memo);
    memo.put(n, result);
    
    return result;
}

// 使用示例
public static void testMemoized() {
    HashMap<Integer, Integer> memo = new HashMap<>();
    int result = fibonacciMemoized(35, memo);
    System.out.println("记忆化递归结果：" + result);
}

优点：

• 保留了递归的逻辑清晰性。
• 时间复杂度优化到 O(n)，空间复杂度 O(n)（用于存储缓存）。

这是一种“既想优雅，又想高效”的解决方案，适合对代码可读性有要求的场景。

总结：掌握 Java 实例 – 斐波那契数列的意义

通过今天的学习，我们不仅实现了斐波那契数列的多种写法，更重要的是理解了算法设计的核心思想：

• 递归：适合表达自相似问题，但要注意性能陷阱。
• 循环：高效、稳定，是生产环境的首选。
• 记忆化：在保持递归结构的同时，提升效率。
• 数组存储：便于批量处理和分析。

这些思维模式，远远超出了“算出一个数”的范畴。它们是解决实际问题的通用工具。当你在面试中被问到“如何优化斐波那契数列”，你能从容说出递归的缺陷、循环的优势、记忆化的原理，就已经远超大多数初学者。

最后，记住：算法不是背题，而是培养思维。 每一次对斐波那契数列的深入探索，都是你在为未来的复杂系统打基础。

希望这篇关于 Java 实例 – 斐波那契数列的完整解析，能成为你编程旅程中的一盏明灯。继续写代码，继续思考，你会越来越接近“高手”的境界。