JavaScript 递归实战：用循环与递归输出单链表（Modern JavaScript Tutorial 精讲）
JavaScript 递归实战：用循环与递归输出单链表（Modern JavaScript Tutorial 精讲）
导读：本文围绕《现代 JavaScript 教程（The Modern JavaScript Tutorial）》中"递归和堆栈"一节的经典习题——输出单链表（
printList）展开。链表是递归定义的数据结构，本任务要求分别用循环与递归两种方式实现逐元素输出，并讨论两者的取舍。读完本文，你将掌握链表遍历的两种典型实现、递归与迭代在内存与性能上的本质差异，以及如何将同一思路推广到反向输出、递归求和等进阶场景。
任务背景：为什么用链表来练递归
在 递归和堆栈 一章中，作者引入了 递归结构（recursive structure） 的概念：一种数据结构可以用自身来定义。链表（linked list）就是教科书级的例子——一个链表元素是包含以下两部分的对象：
value：当前节点存储的值；next：指向下一个链表元素的引用，若为链表末尾则为null。
用代码表示即：
list = { value, next -> list }
本任务所用的链表（见 任务原文）为 4 个节点依次嵌套：
let list = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: {
value: 4,
next: null
}
}
}
};
也可以逐段构造（章节原文）：
let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };
list.next.next.next.next = null;
链表与数组的关键差异在于：数组在首部插入/删除元素需要整体重排（arr.unshift、arr.shift 代价高），而链表只需修改相邻节点的 next 引用即可完成插入与删除（详见章节中的 链表分割示例）。链表因此非常适合"快速插入/删除、无需按下标随机访问"的场景，例如队列与双向队列。
解法一：基于循环（迭代）的输出
官方 题解 给出的循环解法如下：
function printList(list) {
let tmp = list;
while (tmp) {
alert(tmp.value);
tmp = tmp.next;
}
}
printList(list); // 依次弹出 1、2、3、4
实现要点：
while (tmp)以节点对象作为循环条件：只要tmp不是null就继续；- 每次循环先读取
tmp.value输出当前节点，再把tmp前进到tmp.next； - 当走到
next: null的尾节点后，tmp变为null，循环终止。
为什么引入临时变量 tmp
从技术上讲，也可以直接复用入参 list：
function printList(list) {
while (list) {
alert(list.value);
list = list.next; // 修改了入参
}
}
但官方题解明确不推荐这样做，理由有两点：
- 破坏入参：
list本身代表链表（即首节点）。一旦被修改，函数执行完毕后调用方就再也拿不到原链表了。若未来需要扩展函数（例如在输出后继续对链表做其他操作），这个能力就会丢失； - 语义清晰：
list应当保持"链表本身"的含义，而tmp的角色正如for循环中的计数器i——专门负责遍历游走。好的变量命名让代码的意图一目了然。
解法二：基于递归的输出
递归解法的思路非常直接（官方题解）：要输出整个链表，只需输出当前元素，再对 list.next 代表的"其余部分"做同样的事。
function printList(list) {
alert(list.value); // 输出当前元素
if (list.next) {
printList(list.next); // 链表中其余部分同理
}
}
printList(list); // 依次弹出 1、2、3、4
这里体现了递归的两个基本要素：
- 递归步骤：
printList(list)被转化为"输出list.value+ 递归调用printList(list.next)"； - 基础情形（base case）：当
list.next为null（即falsy）时不再递归，函数自然结束。
与 pow(x, n)、sumTo(n) 等数值递归不同，链表递归的"基础"不是数值比较，而是引用是否为 null——这正是递归定义的数据结构天然适配递归遍历的原因。
循环 vs 递归：哪个更好
官方题解的结论非常务实：
从技术上讲，循环更有效。这两种解法做了同样的事，但循环不会为嵌套函数调用消耗资源。另一方面，递归解法更简洁，有时更容易理解。
具体展开如下：
| 维度 | 循环（迭代） | 递归 |
|---|---|---|
| 内存占用 | 恒定，仅一个上下文 | 每个嵌套调用都会在 执行上下文堆栈 中保存上下文，深度为 n 时占用 O(n) 内存 |
| 执行速度 | 更快，无函数调用开销 | 更慢，涉及压栈/出栈 |
| 代码可读性 | 需显式管理 tmp 游标 |
结构与链表定义天然对应，更简洁直观 |
| 深度限制 | 无堆栈深度问题 | 受引擎最大递归深度限制（一般引擎在 10000 以下可靠，100000 很可能超限） |
关于递归深度的限制，章节原文 明确说明："最大递归深度受限于 JavaScript 引擎。引擎在最大迭代深度为 10000 及以下时是可靠的……对于大多数引擎来说，100000 可能就超出限制了。"尾部调用优化（TCO）虽然能缓解这种情况，但目前"还没有被完全支持，只能用于简单场景"。
同章的 对数字求和到给定值 任务也印证了这一点：官方 题解 指出"递归涉及嵌套调用和执行堆栈管理，这会占用资源，因此递归的速度更慢一些"；如果引擎不支持尾调用优化，计算 sumTo(100000) 会因"超出最大堆栈深度"而报错。
因此实践建议是：
- 链表较长、对性能敏感、或可能超过引擎递归深度上限时，优先用循环；
- 链表较短、追求代码简洁与可维护性时，递归是更好的选择——正如 章节原文 所强调的："并不是每个地方都需要优化，大多数时候我们需要一个好代码。"
举一反三：反向输出单链表
紧接着的进阶任务 反向输出单链表 要求以 4、3、2、1 的顺序输出同一个链表，同样用循环与递归两种方式实现。这组练习能帮你更深刻地体会递归与循环在"顺序"处理上的差异。
递归版反向输出
官方题解 的核心逻辑是：先输出链表的其余部分，再输出当前元素——即把 alert 放到递归调用之后：
function printReverseList(list) {
if (list.next) {
printReverseList(list.next); // 先递归深入
}
alert(list.value); // 回溯时再输出
}
printReverseList(list); // 依次弹出 4、3、2、1
其运行原理正是利用了执行上下文堆栈：每次递归调用先把当前节点"记录"在堆栈中，直到触底（list.next === null）后逐层回溯，alert 便以逆序执行。
循环版反向输出
循环无法从链表尾部向前读取（链表只有 next 单向指针），因此官方 题解 采用的策略是：先正序收集到一个数组，再反向遍历数组：
function printReverseList(list) {
let arr = [];
let tmp = list;
while (tmp) {
arr.push(tmp.value);
tmp = tmp.next;
}
for (let i = arr.length - 1; i >= 0; i--) {
alert(arr[i]);
}
}
printReverseList(list); // 依次弹出 4、3、2、1
题解最后点明了一个有趣的等价性："递归解法实际上也是这样做的：它顺着链表，记录每一个嵌套调用里链表的元素（在执行上下文堆栈里），然后输出它们。"——递归的调用栈与循环版的临时数组，本质上是同一思路的两种载体。
小结
围绕"输出单链表"这一经典习题，可以提炼出以下可复用的知识点：
- 链表是递归定义的数据结构：
list = { value, next -> list }，用next === null表示链表终点； - 遍历链表有两种范式：循环版用
tmp游标显式前进；递归版用"输出当前元素 + 递归处理next"表达同一逻辑； - 性能与可读性的权衡：循环省内存、速度快；递归更简洁，但受执行上下文堆栈与引擎递归深度限制；
- 递归反向输出只需把输出动作移到递归调用之后，体现了调用栈天然的"后进先出"特性；
- 通用原则：任何递归都可以用循环重写（章节原文），但当结构复杂、分支众多时，递归往往更易读、更易维护。
如果想继续深入学习递归的应用，同章还提供了 斐波那契数（注意其朴素递归在 fib(77) 时存在性能陷阱）、递归遍历公司薪资求和 等练习；而 递归与堆栈 章节原文则系统讲解了执行上下文堆栈、递归深度限制与尾调用优化的现状，是理解本文所有结论的底层理论基础。