斐波那契数列是编程入门与算法面试中的经典题目，其数学定义为：第1项和第2项均为1，从第3项开始每一项都等于前两项之和。在Java中，我们通常会用递归或循环迭代两种方式去实现它，但两者的性能表现差别极大。理解它们背后的执行机制，有助于在真实业务里写出更高效的代码。
一、基础递归实现及其原理
递归写法最贴近斐波那契的数学定义，逻辑上非常直观：要求第n项，就分别去求第n-1项和第n-2项，直到触底到n为1或2时返回1。这种自顶向下的拆分方式，让代码读起来就像在描述公式本身。
不过，朴素递归存在一个致命问题：大量子问题被重复计算。例如计算fib(5)时需要fib(4)和fib(3)，而fib(4)又需要fib(3)和fib(2)，其中的fib(3)会被求解两次。随着n增大，重复计算量呈指数级增长，时间复杂度约为O(2^n)。
public class FibonacciDemo {
// 基础递归实现
public static long fibRecursive(int n) {
if (n == 1 || n == 2) {
return 1;
}
// 重复计算 fib(n-1) 和 fib(n-2) 的子树
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
public static void main(String[] args) {
int n = 40;
long start = System.currentTimeMillis();
long result = fibRecursive(n);
long end = System.currentTimeMillis();
System.out.println("递归计算第" + n + "项结果:" + result);
System.out.println("耗时:" + (end - start) + "毫秒");
}
}
在上面代码中，当n等于40时，fibRecursive方法会被调用上亿次，在普通笔记本上往往要花费一秒以上。而且由于每次调用都会在调用栈上压入新帧，n过大时还可能触发StackOverflowError。从工程角度看，这种写法只适合用来理解递归思想，不能直接用于生产环境计算较大的n。
二、循环迭代实现与性能优势
循环迭代采取自底向上的思路：从已知的第1项和第2项出发，用两个变量保存前两项的值，每一次循环都计算出新的当前项，然后滚动更新这两个变量。整个过程没有重复计算，也没有调用栈的深层嵌套。
迭代法的时间复杂度是O(n)，空间复杂度仅为O(1)，因为它只用了固定几个long类型变量。对于同样的第40项，迭代版本通常不到一毫秒就能得出结果，性能优势极其明显。
public class FibonacciIterative {
// 循环迭代实现
public static long fibIterative(int n) {
if (n == 1 || n == 2) {
return 1;
}
long prev = 1; // 第 n-2 项
long curr = 1; // 第 n-1 项
for (int i = 3; i <= n; i++) {
long next = prev + curr; // 计算当前项
prev = curr; // 滚动更新
curr = next;
}
return curr;
}
public static void main(String[] args) {
int n = 40;
long start = System.currentTimeMillis();
long result = fibIterative(n);
long end = System.currentTimeMillis();
System.out.println("迭代计算第" + n + "项结果:" + result);
System.out.println("耗时:" + (end - start) + "毫秒");
}
}
这段代码中，for循环从3执行到n，每次仅做三次赋值和一次加法。即使n扩大到百万级别，只要long类型不溢出，迭代法依然能平稳运行。如果结果可能超过long上限，可改用BigInteger来保存数值，但核心滚动逻辑不变。
三、两种写法对比与改进思路
为了更直观地看清差异，我们把关键指标整理成下表：
| 实现方式 | 时间复杂度 | 空间复杂度 | 代码可读性 | 大数据适用性 |
|---|---|---|---|---|
| 基础递归 | O(2^n) | O(n)调用栈 | 高 | 差，易溢出或超时 |
| 循环迭代 | O(n) | O(1) | 中 | 好 |
如果既想要递归的清晰结构，又想避免重复计算，可以采用记忆化递归：用一个数组或HashMap缓存已经算出的项，下次直接取用。此外，若使用支持尾调用优化的语言或通过特定写法，也能将递归转为近似迭代的开销，但Java目前并不做尾递归优化，因此记忆化是更实际的折中方案。
import java.util.HashMap;
import java.util.Map;
public class FibonacciMemo {
private static Map<Integer, Long> cache = new HashMap<>();
// 记忆化递归
public static long fibMemo(int n) {
if (n == 1 || n == 2) {
return 1;
}
if (cache.containsKey(n)) {
return cache.get(n);
}
long value = fibMemo(n - 1) + fibMemo(n - 2);
cache.put(n, value);
return value;
}
public static void main(String[] args) {
int n = 40;
long start = System.currentTimeMillis();
long result = fibMemo(n);
long end = System.currentTimeMillis();
System.out.println("记忆化递归结果:" + result);
System.out.println("耗时:" + (end - start) + "毫秒");
}
}
记忆化递归在首次计算时即可将复杂度降到O(n)，且代码仍然保持自顶向下的表达。对于绝大多数Java应用场景，如果n不太大且追求代码简洁，记忆化递归是不错的妥协；若n很大或处于性能敏感路径，直接使用循环迭代最为稳妥。
四、总结建议
在Java里写斐波那契数列，基础递归适合教学演示，循环迭代适合真实计算，记忆化递归则兼顾了可读与效率。面试中常要求手写递归并现场分析其缺陷，能主动指出指数级重复计算并给出迭代或缓存方案，往往比单纯写出代码更能体现功底。
日常开发中遇到类似“前一项依赖前几项”的序列计算，都可以套用滚动变量或缓存思想。把算法复杂度记在心里，才能在需求变更、数据量上涨时，写出不会突然变慢的程序。