栈和递归是什么关系？为什么递归可能导致栈溢出？

简化版

递归的每一层调用，都会在函数调用栈上压入一个「栈帧」（存参数、局部变量、返回地址），返回时弹出。所以递归本质就是由系统调用栈驱动的。递归太深（层数太多）或没有正确的终止条件，栈帧不断累积、超过栈空间上限，就会 StackOverflowError。任何递归都可以用一个显式的栈改写成迭代。

详细版

调用栈（Call Stack）：程序运行时，每调用一个函数就压入一个栈帧，里面存这次调用的参数、局部变量、返回地址；函数返回时弹出栈帧、回到调用点。这个栈由系统/JVM 管理，空间有限（Java 默认每线程约几百 KB ~ 1 MB）。

递归与栈的关系：递归函数 A 调 A 调 A……每层都占一个栈帧，一层层往上压。直到触底（base case）才开始逐层返回、弹栈。所以：

factorial(3)
 → push factorial(3)
   → push factorial(2)
     → push factorial(1)  // base case，返回 1
     ← pop，返回 2×1=2
   ← pop，返回 3×2=6
 ← pop

栈溢出的两个常见原因：

递归太深：如对一条 10 万节点的链表做递归遍历，10 万层栈帧直接压爆栈。
缺少/错误的终止条件：递归不收敛，无限往下调，栈帧无限增长。

完整版教学

一、递归为什么「自带一个栈」

很多人以为递归是「凭空」实现的，其实它借用了系统调用栈。每次函数调用都必须记住「我从哪来、算到哪、局部变量是什么」，这些信息打包成栈帧压入调用栈；返回时弹出、恢复现场。递归无非是「函数调用自己」，于是调用栈上就叠了一摞同一个函数的栈帧。递归的「记住上一层状态、逐层回退」正是靠栈的后进先出实现的——最后进入的最深一层，最先返回。

二、为什么会栈溢出

调用栈空间是有限的（Java 每个线程有固定栈大小，可用 -Xss 调整）。每层递归吃掉一个栈帧，递归越深、栈帧越多。当层数 × 每帧大小超过栈容量，就抛 StackOverflowError。

深度问题：即使逻辑正确，数据规模让递归深度达到几万几十万层，也会溢出。例如深度很大的树/链表做朴素递归。
不收敛问题：base case 写错或漏写，递归永不停止，必然溢出。

StackOverflowError（栈溢出，递归太深）和 OutOfMemoryError（堆内存耗尽，对象太多）是两回事：前者是调用栈满了，后者是堆满了。别混淆。

三、递归改迭代：用显式栈

任何递归都能改成「用一个显式栈手动模拟调用栈」的迭代版，从而不受系统栈深度限制（改用堆内存里的栈，空间大得多）。以二叉树中序遍历为例：

void inorder(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { stack.push(cur); cur = cur.left; } // 一路压左
        cur = stack.pop();
        visit(cur);
        cur = cur.right;
    }
}

我们用 stack 显式保存「待返回的节点」，替代了系统调用栈的角色。递归转迭代的通用套路就是「把递归调用前后的状态手动压栈/弹栈」。

四、尾递归与优化

尾递归是指递归调用是函数的最后一步（返回值直接是递归结果，不再做额外运算）。有些语言/编译器能做尾递归优化（TCO）：复用当前栈帧而不新建，从而把递归变成循环、不增长栈，避免溢出。但要注意：Java 和 JVM 默认不做尾递归优化，所以在 Java 里深递归即使是尾递归也可能溢出，得手动改成迭代。

五、实战建议

深度可能很大（大树、长链表、大规模 DFS）→ 优先用迭代 + 显式栈，或改 BFS。
深度可控（如平衡树高度 O(log n)）→ 递归简洁清晰，放心用。
递归务必写对终止条件，并确保每次递归都在向它靠近（收敛）。

六、常见误区与追问

递归概念	栈里的对应物	说明
函数调用	栈帧入栈	保存参数、局部变量、返回地址
递归返回	栈帧出栈	回到上一层继续执行
递归深度	栈帧数量	太深会栈溢出
显式栈	手动保存状态	可把递归改成迭代

记忆钩子：递归不是“魔法循环”，它是运行时帮你维护了一摞未完成的函数调用。

以计算 factorial(4) 为例，调用会依次压入 f(4)、f(3)、f(2)、f(1) 四个栈帧；到达边界后，返回值再按 1 -> 2 -> 6 -> 24 一层层弹回。若递归深度变成 100000，栈帧数量也可能接近 100000，超过线程栈限制就会栈溢出。

误区：递归一定比迭代更慢很多。 递归有调用栈开销，但真正是否慢还取决于算法复杂度；指数递归慢通常是重复子问题导致的。
误区：尾递归在所有语言里都会自动优化。 是否做尾调用优化取决于语言和运行时，Java 等常见面试语言不能默认依赖它。
误区：递归改迭代只是把函数名换成 while。 通常要显式保存节点、阶段、返回后的继续位置等状态。
追问：为什么 DFS 常能用栈改写？ 深度优先本质是先处理最近发现但未完成的分支，符合 LIFO。
追问：栈溢出怎么解决？ 降低递归深度、改成显式栈迭代、使用 BFS 或动态规划，或在受控环境调大栈空间。
追问：递归的空间复杂度怎么算？ 看最大递归深度，每层栈帧占常数或额外状态，深度 n 通常是 O(n) 栈空间。

七、加强记忆

递归靠系统调用栈驱动：每层调用压一个栈帧（参数/局部变量/返回地址），返回时弹出，后进先出正好对应「最深一层最先返回」。递归太深或不收敛 → 栈帧堆满 → StackOverflowError（区别于堆满的 OutOfMemoryError）。任何递归都能用显式栈改成迭代以突破系统栈深度限制。Java 不做尾递归优化，深递归要手动改迭代。

简化版

详细版