递归实现斐波那契时间复杂度为指数级，因重复计算导致效率极低；迭代实现时间o(n)、空间o(1)，推荐用于实际项目；int在n>46时溢出，需依需求换用long或biginteger；记忆化仅在多次不同n调用时有效。
递归实现 fibonacci：为什么越写越慢？
直接用递归写 fibonacci(n) 看似简洁，但时间复杂度是指数级的——fibonacci(40) 就要算上亿次调用。根本原因是重复计算：算 fibonacci(5) 时，fibonacci(3) 被算两次；算 fibonacci(10) 时，fibonacci(3) 被算几十次。
如果只是练手或 n ，可以这么写：
public static int fibonacci(int n) {
if (n < 2) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}- 边界必须是
n （即 <code>n == 0返回 0，n == 1返回 1），错写成n 逻辑不变，但可读性略差 - 不处理负数输入的话，
fibonacci(-1)会无限递归栈溢出，加个if (n 更稳妥 - 别用
long或BigInteger递归——递归深度没变，只是延缓了溢出，没解决本质问题
迭代实现 fibonacci：怎么写才不容易错？
迭代是实际项目里该用的方式：时间 O(n)，空间 O(1)，且不会栈溢出。核心是只存最近两个值，滚动更新。
常见写法：
立即学习“Java免费学习笔记（深入）”；
public static int fibonacci(int n) {
if (n < 0) throw new IllegalArgumentException();
if (n < 2) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int tmp = a + b;
a = b;
b = tmp;
}
return b;
}- 循环变量
i从2开始，对应算第 2 项（即fibonacci(2) == 1），别从0或1起，容易多算或少算一轮 -
a和b的初始值必须是fibonacci(0)和fibonacci(1)，顺序不能反，否则结果偏移 - 如果需要返回前
n项，就用List<integer></integer>收集，但注意int在n > 46时就溢出了，这时候得切到long或BigInteger
int 溢出怎么办？什么时候该换类型？
int 最大值是 2147483647，而 fibonacci(47) == 2971215073，已经超了。运行时不会报错，只会静默溢出变成负数——比如 fibonacci(47) 返回 -1323752223。
- 如果明确要支持
n ，改用 <code>long即可（fibonacci(93)才超long） - 若需求是“任意大的
n”，必须用BigInteger，但要注意：它不可变，每次加法都新建对象，性能比long差一个数量级 - 别在迭代里混用类型：比如
a用int、b用long，容易因自动提升引发隐式截断
要不要加缓存？memoization 在什么场景真有用？
纯递归加缓存（记忆化）能把时间压到 O(n)，但它只在「多次调用不同 n 值」时才划算。比如你反复调用 fibonacci(10)、fibonacci(15)、fibonacci(10)，缓存才有意义。
- 单次调用
fibonacci(100)，缓存数组要开 101 个槽，不如直接迭代省空间 - 缓存用
int[] memo = new int[n + 1]最简单，但要注意初始化：全填 -1，因为fibonacci(0) == 0是合法值，不能用 0 当“未计算”标记 - 并发环境下别直接共享
memo数组，除非加锁或改用ConcurrentHashMap
边界小、调用散、又懒得改迭代逻辑时，缓存递归是折中选择；其他情况，迭代更干净利落。
