递归实现斐波那契：为什么 fib(50) 会卡住
直接写 fib(n) 递归函数很简洁，但不加优化时，fib(45) 就明显变慢，fib(50) 可能要等好几秒——这不是 JVM 慢，是算法本身重复计算了指数级子问题。比如算 fib(5) 时，fib(3) 被调用了两次，fib(2) 被调用了三次，以此类推。
常见错误现象：StackOverflowError 很少见（除非 n > 10000），但 CPU 占用高、响应迟缓才是实际痛点。
- 基础写法就是
return n - 时间复杂度是
O(2^n)，不是O(n)，别被“只写了两行”骗了 - Java 默认栈深度约 10000 层，
fib(10000)才真会爆栈，日常用不到那么大
加个缓存就快了：用 HashMap 记住算过的值
这是最贴近“递归入门”需求的改进——不动结构，只加记忆化。核心是避免重复调用同一 n 对应的 fib(n)。
使用场景：需要保持递归逻辑清晰、又不能接受指数级耗时的场合，比如教学演示或小规模动态查询。
立即学习“Java免费学习笔记（深入）”；
- 声明一个
Map<integer long></integer>（注意用Long，int在n > 46时就溢出） - 每次进入函数先查 map，存在就直接返回；不存在才递归计算并存入
- 别用
staticmap 全局共享——多线程下不安全；要么传参，要么用线程局部变量
Map<Integer, Long> memo = new HashMap<>();
long fib(int n) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
long res = fib(n-1) + fib(n-2);
memo.put(n, res);
return res;
}
别在生产代码里用纯递归：fib(n) 的替代方案
真要算第 100 万个斐波那契数？递归再怎么优化也不合适。Java 标准库没提供现成工具，得自己选路。
参数差异和取舍点：
-
int n小（long 存结果，3 行搞定，无开销 -
n中等（47–10000）：用BigInteger迭代，避免溢出，空间O(1)，时间O(n) -
n很大（> 10^5）：考虑矩阵快速幂或 Binet 公式近似——但 Java 浮点精度扛不住，慎用 - 千万别为了“体现递归思想”在线上服务里写未记忆化的
fib(n)，监控会报警
为什么不用 @Memoized 或 Lombok？
有人想用注解自动缓存，比如 Lombok 的 @Memoized，但 Java 原生不支持，第三方方案有硬伤。
容易踩的坑：
-
@Memoized是 Lombok 编译期生成，缓存是实例字段，无法控制生命周期，可能内存泄漏 - 它不支持参数校验（比如
n ），异常处理不透明 - 缓存 key 是整个参数列表，而
fib只有一个int，大材小用还引入了额外依赖 - 面试时写这个，不如手写 5 行
HashMap清晰——考的就是你懂“为什么缓存有效”，不是“会不会粘贴注解”
递归本身不难，难的是意识到哪一层该截断、哪一步该缓存、哪个数据类型会悄悄越界。这些地方一不留神，程序就从“运行正确”变成“运行缓慢但结果对”，后者更难排查。
