Appearance
第 11 章 显式栈：把递归换成迭代
📖 邮差的回程票
体检完的第二天，小铃早早来到老墨的办公室——第三部分"优化之路"的图纸已经摊开在桌上了。
第一张图纸画的是传播。可小铃盯着图纸看了半天，总觉得哪里不对。
"老墨，"她指着图纸说，"邮差走到中转站，要下钻到它的听众；走完再回来，继续走同层的下一站——这不就是我们第 8 章写的递归吗？为什么要重画？"
"问得好。"老墨放下茶杯，"递归有个隐藏的代价，你知道吗？"
小铃摇头。
"递归每下钻一层，程序就要在调用栈（call stack）上占一格'跳板'——记住'我是从哪下来的，回去要接着走哪'。第 8 章我们写的传播，每碰到一个中转站就往下跳一层，跳完再跳回来。"老墨在图纸上画了一个越来越深的楼梯，"消息城现在只有几个节点，无所谓。可老墨的梦想，是让信号库去处理几百万个节点的大图——"
"到那时……"
"到那时，楼梯会深到跳板不够用。程序'啪'地一声崩掉，这叫栈溢出（stack overflow）。"老墨拍了拍图纸，"所以，真实的信号库不用递归——它让邮差自己背着一沓回程票走。"
"回程票？"
"对。下钻之前，先买一张票，记着'这一层还有哪一站没走'；走完一层，掏出票，回到上一层接着走。路记在自己手里，不占程序的一格跳板——楼梯多深都不怕。这个'自己背票走路'的办法，叫显式栈（explicit stack），也叫迭代（iteration）。"
小铃看着图纸上邮差口袋里那沓票，跃跃欲试："那……改起来大吗？"
"不大。传播干的事一个字都不变——盖章、排队、下钻。变的只是'怎么记住回去的路'：从'靠程序跳板'，换成'靠自己的回程票'。"
🎯 本章要解决什么
一句话问题：怎么把传播的递归换成显式栈（迭代），干的事一模一样，却不再依赖调用栈？
读完这一章，你会知道：
- 递归的隐藏代价：调用栈和栈溢出；
- 什么是回程票（显式栈），邮差怎么用它走路；
- 为什么说"行为一模一样，只是换了个记路的方法"——23 条测试一个字都不用改。
💡 概念讲解
递归的代价：调用栈（跳板）
程序每调用一个函数，都要在调用栈上压一格"跳板"，记着"这个函数是从哪被叫的，办完事回哪去"。
递归下钻几层，跳板就压几格：
mermaid
graph TD
p1["传播（第 1 层）🪜"] --> p2["传播（第 2 层）🪜"]
p2 --> p3["传播（第 3 层）🪜"]
p3 --> pn["传播（第 N 层）🪜"]
pn --> boom["栈溢出 💥"]图特别深（几百万个节点）的时候，跳板会用完——程序崩掉。这就是栈溢出。
显式栈：自己背回程票
换一个思路：不让程序记路，让邮差自己记。
邮差的手里攥着一沓回程票（tickets），规则只有两条：
- 下钻之前：如果这一层还有下一站没走，买一张票，记下"这一层剩下的路"；
- 一层走完：掏出最上面那张票（后买的先掏），回到上一层接着走。
mermaid
graph LR
a["a 的听众链：c1 → c2 → E2"] --> c1["下钻 c1 🧮"]
c1 --> e1["c1 的听众：E1 🧒<br/>（买票：同层还有 E2）"]
e1 --> back["走完，掏票回到 E2 🎫"]
back --> e2["E2 🧒"]"后买的先掏"有个正式名字：栈（stack），也叫后进先出（LIFO）——像一摞盘子，最后放上去的最先拿走。数组的 push（放上去）和 pop（拿下来），正好就是栈的两种动作。
为什么"行为一模一样"
第 8 章的递归和这一章的显式栈，走的路线完全一样：同一个顺序盖章、同一个顺序排队。变的只是"记住回去的路"的方式：
| 递归 | 显式栈 | |
|---|---|---|
| 路记在哪 | 程序的调用栈（跳板） | 邮差自己的回程票 |
| 图很深时会怎样 | 跳板用完，栈溢出 💥 | 票在自己手里，多深都不怕 |
| 代码长相 | propagate(sub.subs)（调自己） | while 循环 + 买票/掏票 |
所以：23 条测试一个字都不用改——它们验证的是"传播干了什么"，而这一章，传播干的事一点没变。
✍️ 动手写代码
今天只改一个函数：propagate。把"调自己"换成"while 循环 + 回程票"。
第 1 步：换掉 propagate
打开 src/signal.ts，找到 propagate，整个替换成：
ts
// 传播：把递归换成显式栈——邮差自己扛着"回程票"走
function propagate(link: Link): void {
const tickets: Link[] = []; // 回程票：记着从哪下来的，回去继续走
let l: Link | undefined = link; // 现在站在哪根线上
while (l !== undefined) {
const next: Link | undefined = l.nextSub; // 同层的下一站（先记住，防迷路）
const sub: ReactiveNode = l.sub;
const flags = sub.flags;
if (!(flags & (ReactiveFlags.Pending | ReactiveFlags.Dirty))) {
sub.flags = flags | ReactiveFlags.Pending; // 盖"待核实"章
if (flags & ReactiveFlags.Watching) {
notify(sub as EffectNode); // 自动反应：排队
} else if (flags & ReactiveFlags.Mutable && sub.subs !== undefined) {
if (next !== undefined) {
tickets.push(next); // 这一层还有路：买张回程票
}
l = sub.subs; // 下钻：往它的听众走
continue;
}
}
l = next ?? tickets.pop(); // 同层下一站，或掏出回程票
}
}对照第 8 章的递归版，逐段看：
- 盖章、排队：一个字没变——
Pending章、notify排队，还是老规矩； - 下钻：递归版写
propagate(sub.subs)（调自己）；现在写l = sub.subs（把"要走的线"换成它的听众链头），再continue回 while 循环继续走； - 回程票：下钻前，如果这一层还有下一站（
next !== undefined），把它压进tickets；走到底时，tickets.pop()把最上面的票掏出来，回到上一层。
第 2 步：叫检查员！（回归）
bash
npm test🚀 现在跑一下，你应该看到：
✓ tests/checkup.spec.ts (2 tests) ✓ tests/checkdirty.spec.ts (2 tests) ✓ tests/subscription.spec.ts (2 tests) ✓ tests/naive-problems.spec.ts (2 tests) ✓ tests/batch.spec.ts (4 tests) ✓ tests/computed.spec.ts (4 tests) ✓ tests/signal.spec.ts (5 tests) ✓ tests/money.spec.ts (2 tests) Test Files 8 passed (8) Tests 23 passed (23)23 个，一个都不红。 这就是"行为一模一样"的铁证——我们只是换了记路的方式，传播干的事一点没变。🎉
🧰 TS 小课堂：??（空值合并）
今天的新语法藏在最后一行里：
ts
l = next ?? tickets.pop();?? 读作"空值合并"：左边是 undefined（或 null），就用右边；否则用左边。
next有值（这一层还有下一站）→ 用next；next是undefined（这一层走完了）→ 用tickets.pop()（掏回程票）。
它是 next !== undefined ? next : tickets.pop() 的短写法——一样的意思，更短、更清楚。
小心别和 || 搞混
|| 是"左边是假的就用右边"（0、'' 也算假）；?? 只认 undefined 和 null。数字 0 是"真值"，0 ?? 5 是 0，0 || 5 却是 5。记：?? 只管"空"，不管"假"。
📚 本章用语
| 词 | 意思 | 记住它 |
|---|---|---|
| 调用栈 (call stack) | 程序记"函数从哪来、回哪去"的跳板 | 递归每层压一格 |
| 栈溢出 (stack overflow) | 跳板用完了，程序崩掉 | 图太深就会发生 |
| 栈 (stack) | 后进先出的一摞东西 | 一摞盘子，后放的先拿 |
| 显式栈 | 自己用数组 push/pop 记路 | 回程票在自己手里 |
| 迭代 (iteration) | 用循环代替递归 | 不调自己，走 while |
这些是本章用语——"栈"是程序员的通用概念，不进书末尾的正式词典。
📦 章末完整代码
这一章你只换了一个函数，文件夹结构一个字没变：
signal-book/
├── demo/
│ └── ch01.mjs
├── node_modules/
├── package.json
├── tsconfig.json
├── src/
│ ├── money.ts
│ └── signal.ts ← 只换了 propagate（其余和第 9 章一模一样）
└── tests/
├── money.spec.ts
├── signal.spec.ts
├── computed.spec.ts
├── batch.spec.ts
├── naive-problems.spec.ts
├── subscription.spec.ts
├── checkdirty.spec.ts
└── checkup.spec.tssrc/signal.ts 的其他部分和第 9 章"章末完整代码"里那份一模一样——不需要重抄。只有 propagate 换成了第 1 步的迭代版，再贴一遍供对照：
ts
// 传播：把递归换成显式栈——邮差自己扛着"回程票"走
function propagate(link: Link): void {
const tickets: Link[] = []; // 回程票：记着从哪下来的，回去继续走
let l: Link | undefined = link; // 现在站在哪根线上
while (l !== undefined) {
const next: Link | undefined = l.nextSub; // 同层的下一站（先记住，防迷路）
const sub: ReactiveNode = l.sub;
const flags = sub.flags;
if (!(flags & (ReactiveFlags.Pending | ReactiveFlags.Dirty))) {
sub.flags = flags | ReactiveFlags.Pending; // 盖"待核实"章
if (flags & ReactiveFlags.Watching) {
notify(sub as EffectNode); // 自动反应：排队
} else if (flags & ReactiveFlags.Mutable && sub.subs !== undefined) {
if (next !== undefined) {
tickets.push(next); // 这一层还有路：买张回程票
}
l = sub.subs; // 下钻：往它的听众走
continue;
}
}
l = next ?? tickets.pop(); // 同层下一站，或掏出回程票
}
}✅ 跑通了？ 只要
npm test打出23 passed，邮差的回程票就缝好了——干的事一模一样，路却记在自己手里了。
🎮 动手试试
怎么玩
先自己写答案，再点开对照。忍得住才点开哦！
1. 预言输出（猜一猜）
小铃搭了一条"岔路"：a → c1 → E1，还有一条直达的 a → E2。猜猜 logs 最后长什么样？
ts
const logs: string[] = [];
const a = signal(1);
const c1 = computed(() => a() * 2);
effect(() => {
logs.push('E1');
c1();
});
effect(() => {
logs.push('E2');
a();
});
a(5);👉 点开看答案
logs 是 ['E1', 'E2', 'E1', 'E2']。
- 注册时：E1 先跑一遍（push 'E1'），E2 再跑一遍（push 'E2'）；
a(5)变化时：传播先走到c1（下钻），把 E1 排队；再回到同层，把 E2 排队——先下钻的订报人先跑，所以是 E1、E2。
排队顺序就是传播的走路顺序——递归和显式栈走的路一模一样，所以顺序也一模一样。
2. 帮小铃找 bug（抓错）
小铃写迭代版时，把两行重要的代码忘了：
ts
} else if (flags & ReactiveFlags.Mutable && sub.subs !== undefined) {
l = sub.subs;
// 咦？少了 continue，也少了买票！
}结果：测试红了——E1 再也不跑了。为什么？
👉 点开看答案
少了 continue，程序会掉出 if，执行最后一行的 l = next ?? tickets.pop()——把刚换好的 l（sub.subs，下钻的路）又覆盖成同层的下一站了。下钻的路被丢掉，c1 的听众（E1）永远走不到，自然再也不跑。
少了买票，就算补上 continue，下钻完也会丢掉"同层还有 E2 没走"的记忆——E2 也会被漏掉。
正确写法缺一不可：
ts
if (next !== undefined) {
tickets.push(next); // 买票：记住同层剩下的路
}
l = sub.subs; // 下钻
continue; // 别让下面的代码覆盖 l！3. 填空（补全）
迭代版最后一行少了一半，补全它：
ts
l = next ?? /* 这里该写什么？ */;👉 点开看答案
写 tickets.pop()：
ts
l = next ?? tickets.pop();这一层的下一站没了（next 是 undefined），就掏出最上面的回程票，回到上一层接着走。
4. 小挑战（深链）
用 for 循环造一条 100 层的中转站链（每个计算值都依赖上一个，+1），最后挂一个订报人。改一次源头的信号，验证最底层的订报人正确更新。
再想一想：如果消息城的图有几百万层，递归会栈溢出，显式栈为什么不怕？
👉 点开看答案
一种写法：
ts
const base = signal(1);
let chain: () => number = () => base();
for (let i = 0; i < 100; i++) {
const prev = chain;
chain = computed(() => prev() + 1);
}
const logs: number[] = [];
effect(() => {
logs.push(chain());
});
expect(logs).toEqual([101]);
base(2);
expect(logs).toEqual([101, 102]);100 层下钻，传播的tickets最多攒 99 张票——全在邮差自己手里，程序调用栈一格都不占。图再深，也只是票多几张，不会栈溢出。递归就不一样了——每层占一格跳板，深到几万层就会崩。这就是真实信号库把递归换成显式栈的原因。
🏁 本章小结
- 递归有个隐藏代价：每下钻一层占一格调用栈（跳板），图太深会栈溢出、程序崩溃；
- 显式栈让邮差自己背回程票（
tickets数组 +push/pop）：下钻前买票记住同层剩下的路，走完一层掏票回去——路记在自己手里； - 传播干的事一个字没变——23 条测试全绿就是铁证：递归和迭代，只是"记路"的方式不同。
回程票缝好了。老墨在第二张图纸上写下标题：
核实的递归，也换成回程票。
下一章，把 checkDirty 的递归也换成迭代——让"打电话核实"也一样不怕深。