递归在java中易崩而非慢，因jvm默认栈仅约1mb，深度超1000即风险高，超5000基本不可靠；尾递归不被支持，需用stack手动模拟调用栈并显式维护状态与结果。
为什么递归在Java里容易崩，而不是慢
Java递归不是“慢一点”的问题，是StackOverflowError一来就直接挂。JVM默认栈大小通常只有1MB左右（取决于启动参数），而每次递归调用都要压一个栈帧——保存局部变量、参数、返回地址。哪怕只是factorial(10000)，也大概率爆栈；更别说树深度200+的DFS遍历。
- 递归深度 > 1000 就该警惕，> 5000 基本不可靠
- 不是所有递归都能被JIT优化（比如尾递归，Java至今不支持）
- 错误堆栈很长，但真正有用的线索往往只在最顶上几层
怎么用Stack手动模拟递归调用栈
核心思路：把“函数调用”变成“往栈里存状态”，把“返回值合并”变成“出栈后更新结果”。这不是技巧，是还原JVM本来就在做的事。
- 每个入栈元素，对应原递归中一次未完成的调用状态（比如当前
n、当前节点node、当前区间[left, right]） - 出栈时，不做函数调用，而是直接处理这个状态，并决定是否继续压新状态（比如
n-1、子节点、拆分后的子区间） - 必须显式维护结果变量（如
result或sum），不能依赖递归的隐式返回链
以阶乘为例：
public int factorial(int n) {
Stack<Integer> stack = new Stack<>();
stack.push(n);
int result = 1;
while (!stack.isEmpty()) {
int cur = stack.pop();
if (cur <= 1) continue; // base case: 0! = 1! = 1
result *= cur;
stack.push(cur - 1);
}
return result;
}
哪些递归改循环后反而更难懂？别硬转
不是所有递归都适合改成显式栈循环。强行转换会牺牲可读性，还可能引入新bug。
- 纯尾递归（如
tailSum(n, acc)）——直接用while+变量更新就行，根本不用Stack - 多分支且状态耦合强的（如带回溯的排列生成、N皇后）——用
Stack模拟反而要手动管理“撤销”逻辑，易错 - 递归本身已加了记忆化（
memo[n]）——改成循环后，缓存策略得重设计，未必省事
判断信号：如果你画不出清晰的状态转移图，或者栈里要塞多个字段（比如new NodeWithState(node, depth, visitedLeft)），那就先别动，优先考虑迭代替代方案或增大栈空间（-Xss2m）。
立即学习“Java免费学习笔记（深入）”；
快速排序这类分治递归，怎么安全落地为循环
quickSort爆栈不是因为n大，而是最坏情况下递归深度O(n)，比如已排序数组+固定轴点。循环化关键是把“待排序区间”作为状态压栈，而非递归调用本身。
- 栈里只存
int[] range = {left, right}，不存数组副本或中间变量 - 每次出栈后，做一次partition，然后把**较小的子区间先压栈**（优化栈深度，避免最坏O(n)）
- 不需要模拟完整的递归展开顺序——只要保证每个区间都被处理过即可
关键点：if (pivotIndex - left > right - pivotIndex) 决定哪个子区间后处理，能将最大栈深从O(n)压到O(log n)。
递归转循环真正的难点不在语法替换，而在“状态抽象”——你得想清楚，原递归里哪些信息是必须保留的，哪些是每次调用时临时生成又立刻丢弃的。漏掉一个边界条件，或压错一个子状态，循环就悄无声息地算错结果，比StackOverflowError更难排查。
