递归实现斐波那契因重复计算子问题导致时间复杂度达O(2ⁿ)，如fib(45)耗时约3800ms；应改用滚动变量迭代法（O(n)时间、O(1)空间），n≤46用int，47≤n≤92用long，n≥93必须用BigInteger。
Java里用递归写fibonacci为什么慢得离谱
因为每次调用都重复算相同子问题，时间复杂度是 O(2^n)。比如算 fib(5)，fib(3) 会被算两次，fib(2) 算三次——这不是写代码，是在给 JVM 拖后腿。
常见错误现象：fib(45) 就开始明显卡顿，fib(50) 可能让你怀疑电脑死机了；堆栈溢出倒不太容易见，但 CPU 占用会飙高。
- 别在生产代码里直接用裸递归实现
fibonacci - 如果真要递归，必须加记忆化（比如用
HashMap<integer long></integer>缓存结果） - 注意整数溢出：用
int最多算到fib(46)就溢出，建议起步就用long
循环迭代版fibonacci怎么写才安全又快
用两个变量滚动更新，空间 O(1)、时间 O(n)，是实际项目里最该用的写法。
使用场景：需要频繁调用、对响应延迟敏感（比如实时行情计算中间值）、或 n 可能大于 100 的情况。
立即学习“Java免费学习笔记（深入）”；
- 初始化用
long a = 0, b = 1，避免从int开始隐式溢出 - 边界处理要明确：
n == 0返回0，n == 1返回1，别漏掉 - 循环从
i = 2开始，每次算long next = a + b，然后更新a = b; b = next; - 别用数组存全部中间结果——除非你后续真要随机访问任意项
BigInteger什么时候必须上，又该怎么用
当 n 超过 92，long 就撑不住了（fib(93) ≈ 1.2 × 10¹⁹，超出 Long.MAX_VALUE）。这时候不换 BigInteger，结果就是错的，不是慢的问题。
性能影响明显：BigInteger 加法比 long 慢一个数量级以上，但至少结果对。别为了“看起来快”硬扛溢出。
- 声明变量用
BigInteger a = BigInteger.ZERO和BigInteger b = BigInteger.ONE - 加法写成
a.add(b)，不是+；别漏掉new BigInteger("0")这种低效写法 - 如果只需求第 n 项，依然用滚动变量，别建长度为 n 的
BigInteger[]
递归 vs 迭代的实际性能差距有多大
在 JDK 17、普通笔记本上实测：fib(45) 递归耗时约 3800ms，迭代只要 0.005ms——差了 76 万倍。这不是“有点慢”，是根本不在一个量级。
容易被忽略的一点：JVM 的 JIT 编译器对简单循环极度友好，但对深度递归几乎不优化。而且递归每层都有栈帧开销，而迭代就两个变量。
- 别信“现代 JVM 会优化递归”这种话——它不会把指数级变线性级
- 微基准测试要用
JMH，但哪怕用System.nanoTime()粗略测，差距也一眼可见 - 如果面试官问“怎么优化斐波那契”，答“改成迭代”只是及格；补一句“再根据 n 大小决定用 long 还是 BigInteger”才算到位
真正麻烦的从来不是写出来，而是想清楚 n 的取值范围、结果精度要求、以及有没有人会拿 fib(-1) 来试你。
