qinghuan
← 回到知识探索

计算机趣闻 / 动手实验

函数只写了几行，为什么递归会撑爆栈？

每次调用都可能留下待办事项，程序要有地方记住它们。

约 7 分钟含页面互动实验资料核对：2026-09-26
展开本文目录
  1. 先动手看看
  2. 下一层返回之前，上一层还不能走
  3. 先看三层怎样进去，又怎样回来
  4. 能结束，与能在有限空间内结束，是两回事
  5. 换成循环时，想清楚待办事项去了哪里
  6. 记住这三点
  7. 别把例子用过头
  8. 自己试一小步
  9. 查原始资料
  10. 找一份资料继续练
开始前，会这些就够了
  • 理解函数调用和 return
  • 能读懂 if 判断
遇到不熟悉的词，先看这 4 个解释
递归
递归是函数直接或经过其他函数再次调用自己的做法，常把大问题拆成同类的小问题。设计时要说明何时停止，以及每一步为什么确实更接近停止条件。
调用栈
调用栈保存当前尚未结束的函数调用记录，让程序知道被调用的函数完成后应回到哪里继续。层层调用时记录随之增加，返回时再逐层移除或恢复前一层。
线程
线程是进程中被安排执行的一条运行路线。同一进程可以有多个线程，共用部分数据和资源，同时各自保存执行位置与调用记录，因此协作时要留意互相影响。
内存
这里的内存主要指程序运行时使用的随机存取内存，用来放当前要处理的代码和数据。它适合频繁读写，普通电脑中的这类内存通常不能在断电后保留内容。
打开完整术语小抄 ↗

计算从一加到三，可以写成“三加上从一加到二”，继续拆下去直到零。递归把这种说法直接写成函数，但代码只有几行，不代表运行时只需要几行代码那么大的空间。每一层尚未结束的调用，都可能有自己的待办事项。

一层层进去，再一层层回来

用按钮走一小步。注意最晚进入的调用先返回，前面的调用还在等它。

第 1 / 9 步：准备计算 sum(3)。

最近一次返回值：尚未返回

尚未结束的调用：0 层

当前没有尚未结束的调用。

这是有界的调用顺序示意，用卡片表示未完成的工作，不是浏览器真实内存布局。输入只提供 0、3、5，不通过制造深递归探测崩溃极限。

下一层返回之前，上一层还不能走

计算 sum(3) 时，程序先记住“等 sum(2) 返回后，再加三”。计算 sum(2) 时，又要记住“等 sum(1) 返回后，再加二”。这些工作有先后顺序：最里面的计算先完成，外面的调用才逐层接着做，不能提前把待办内容丢掉。

调用栈就是帮助程序追踪这些调用与返回位置的机制。每层记录可以叫栈帧，保存所需数据和运行状态。不同语言和实现的具体结构不完全相同；例如 Java 虚拟机规范明确定义了每次方法调用的帧。纸上画几张叠起来的卡片，是理解顺序的辅助，不是内存布局图。

先看三层怎样进去，又怎样回来

下面把输入限制在零到十的整数，避免为了观察现象故意制造很深的调用。先看进入记录，再看返回记录：到达零以后，不再创建更深的一层，结果沿着之前留下的路线返回。局部变量 result 是各次调用自己使用的记录，并非所有层共享同一个临时格子。

递归最容易被误读的地方，是只看到一直向下调用，却忘了调用后面还会继续执行。这里加法发生在较小问题已经算完之后。理解这条返回路径，比背下“递归等于自己调用自己”更有助于检查真实程序。

小实验 · javascript
function sum(n) {
  if (!Number.isInteger(n) || n < 0 || n > 10) throw new RangeError("use 0..10");
  console.log("enter", n);
  if (n === 0) return 0;
  const result = n + sum(n - 1);
  console.log("leave", n, result);
  return result;
}
console.log("total", sum(3));

怎样运行：在浏览器控制台或 Node.js 中运行。输入有明确的小范围检查，无需故意触发栈溢出。

运行后对照结果
enter 3
enter 2
enter 1
enter 0
leave 1 1
leave 2 3
leave 3 6
total 6

能结束，与能在有限空间内结束，是两回事

第一类问题是根本走不到终止条件。例如规定 n 等于零就停，却允许从负数开始每次再减一，就会越走越远。第二类问题是终止条件正确，但要连续深入很多层。即使数学上最终会到零，运行环境也可能先用尽允许的调用栈空间。

因此不能只检查有没有 if，还要检查每一步是否向终点靠近、允许什么输入，以及最深可能到多少层。不同引擎、函数内容和运行配置会影响可用深度，不应记住一个固定数字当成所有电脑的安全上限。异常名称也可能随语言和引擎变化。

换成循环时，想清楚待办事项去了哪里

这个累加问题可以用循环维护当前数字和总和，不需要保留一整串尚未完成的函数调用。但遍历多层目录或树结构时，递归常能直接表达问题结构；改成循环后，可能仍要自己准备一个数组来存放待访问节点，空间需求并不会凭空消失。

选择时可以先画出最深路径，而不只数总共有多少节点。只有三层、每层分支很多的树，与一条很长的链，调用深度不同。若输入来自外部，应给规模和深度设置明确限制。靠不断调大栈容量掩盖没有终点的错误，只会让失败来得更晚。

记住这三点

  • 递归要保留尚未结束的调用，因此短代码也可能需要很深的调用栈。
  • 终止条件必须可到达，最大深度也要在运行环境能承受的范围内。
  • 循环可能减少调用栈使用，但待处理数据仍可能需要额外空间。

别把例子用过头

  • 没有适用于所有语言、函数和电脑的固定递归安全层数。
  • 画出的卡片解释调用关系，不代表栈帧一定按相同物理方式存储。
  • 本文没有要求触发崩溃，也没有把提高栈大小作为通用修复。

自己试一小步

把 sum(3) 改写为循环后，哪些记录还需要保留？

  1. 先在纸上记录递归每层的 n 和等待完成的操作。
  2. 写一个限制同样输入范围的循环版本，比较小输入的结果。
  3. 再画一棵浅而宽的树和一条长链，标出各自最深调用路径。

做到这些，就算完成

  • 能解释递归的返回顺序，而不只列出进入顺序。
  • 能区分节点总数与最大深度。
  • 循环版本仍正确处理零和无效输入，练习不通过超大输入试探崩溃极限。

查原始资料

想确认一个细节，先看这份资料对应的部分，不必从头读完所有文档。

找一份资料继续练

先选一项，按下面的范围继续学；不必从头读完整门课程。