Lecture 13: 递归 (Recursion)
Lecture 13: 递归 (Recursion)
概述
本讲要解决的问题是：如何用”函数调用自己”来描述那些天然自相似的问题——斐波那契、迷宫、汉诺塔、 二分查找、树的遍历。引入的机制是递归函数 (recursive function)：由基本情况 (base case) 与 递归情况 (recursive case) 构成，每一次调用在运行时都对应一次真实的 JSR 与一个新栈帧 (stack frame)。 递归把 ECE 120 的栈抽象与调用约定同”分而治之”思维缝合在一起：向上承接栈帧与调用约定， 向下开启基于指针的树、链表以及归并/快速排序。
核心概念与底层机制图解
- 递归函数 (Recursive Function)：在自身定义中调用自己，把大问题化成同形的更小问题。
- 直观解释：俄罗斯套娃——打开一层，里面还是同样形状、只是更小；最小的那层打不开，就是基本情况。
- 底层机制图解：递归在机器层面没有任何新指令，它就是
JSR（返回地址存入R7）加栈操作； 每次调用压入一个新帧，放参数、局部变量、返回地址与返回值槽。于是 “递归深度 = 同时存活的帧数”，”递归成本 = 帧大小 × 深度”。 - 作用域与存储期：帧内局部变量是 automatic storage duration，每次调用重新创建、地址各异、随帧销毁； 这正是递归成立的关键——第 4 层的
n与第 1 层的n是两个不同单元。若声明为static（static storage duration），所有层共享同一单元，递归立刻出错。
- 基本情况与递归情况 (Base Case / Recursive Case)：前者给出最小问题的答案并停止递归，后者把问题缩小后交给自己。
- 直观解释：上楼梯——”再上一级”是递归情况，”到一楼就不再往上问”是基本情况。
- 底层机制图解：二者的分界就是”不再执行
JSR的那条分支”。课程模板是 ①检查停止条件 ②处理当前结点 ③处理子结点；②与③可互换，互换后得到先序/后序两种顺序 （print_reverse正是靠它把字符串反着打印）。 - 作用域与存储期：停止条件必须保证参数向基本情况收敛，否则栈持续向低地址增长， 越过栈区边界后进程被操作系统以段错误终止。
- 递归树 (Recursion Tree)：每次调用画成一个结点，其子结点是它发起的调用。
- 直观解释：家族树——每个”人”下面挂着它生出的所有”孩子”。
- 底层机制图解：树的形状直接决定代价：链状树是线性时间；带大量重复子树的二叉树（朴素 Fibonacci） 是指数时间；完全二叉树（汉诺塔）有 2^n 个结点。必须区分两个量： 树高 = 栈帧峰值 = 内存占用，结点总数 = 调用次数 = 时间开销。
- 作用域与存储期：同层不同分支的结点互相不可见（局部变量各在帧里）， 这正是回溯算法退出分支后能”自动恢复现场”的原因。
- 返回阶段 / 回退 (Unwinding)：基本情况返回后控制权逐层回到调用者，每层继续执行调用点之后的语句。
- 直观解释：往里走时把待办事项写在便签上贴墙，走到尽头后往回走，一张张撕下来照做。
- 底层机制图解：
RET把R7装回PC，同时复位R6/R5，该帧内存随即失效（不是清零，只是不再属于你）。print_reverse靠回退阶段完成工作：打印发生在递归调用返回之后，所以字符被反序输出。 - 作用域与存储期：回退后被调用帧的局部变量存储期结束，因此返回指向本帧局部变量的指针 （
char* f(void){ char buf[10]; return buf; }）是经典的悬空指针错误。
- 递归 vs 迭代 (Recursion vs Iteration)：
- 直观解释：递归像贴一叠便签再逐张撕下，迭代像用一张便签反复改写。
- 底层机制图解：递归把进度信息交给栈帧（编译器管理），迭代把它放进循环变量（程序员管理）。 递归代码更短、更贴近数学定义，但有帧建立/拆除开销且深度受栈限制；迭代没有帧开销， 但表达树形结构与回溯时往往要手写显式栈。
- 作用域与存储期：递归的中间状态随帧自动生灭，迭代的中间状态由你负责初始化—— 忘记重置循环变量正是”脏状态”错误的来源。
- 尾递归 (Tail Recursion)：递归调用是整个函数的最后一个动作（
return f(...);，返回后不再计算）。- 直观解释：接力赛——棒子交出去后自己就可以离场，不必站在原地等结果。
- 底层机制图解：调用者的帧此后不再被使用，编译器可复用当前帧，把
JSR 自己改成BRnzp 函数入口（尾调用优化, tail-call optimization），栈深度由 O(n) 降到 O(1)。课程的二分查找就是尾递归。 作用域与存储期：是否优化取决于编译器与优化级别，
-O0下不优化，深度仍受栈限制。 随附的r8_tail_opt.c让一个尾递归函数递归一千万层，三种编译方式的实测结果：编译方式 实测结果 gcc -g -std=c99（即-O0）段错误，退出码 139 gcc -O1正常输出 count_down (10000000) = 10000000，退出码 0gcc -O2 -fno-optimize-sibling-calls段错误，退出码 139 objdump -d显示-O0版本里是一条自己调用自己的callq（真的压帧）， 而-O1版本已经没有自己的帧，改用jne跳回函数开头：-O0: 401159: callq 401126 <count_down> ← 一千万层把 8 MiB 栈撑爆 -O1: 40112c: jne 40112f <count_down+0x9> ← 尾调用优化：回跳，不压帧结论：尾递归是否省栈取决于编译器是否做尾调用优化，
-O0下不省。 不要指望”我写的是尾递归所以不会爆栈”。
- 数组与字符串上的递归 (Recursion over Arrays and Strings)：把”数组的其余部分”当作子问题。
- 直观解释：数一串珠子——”这一颗 + 剩下那一串的数目”，剩下那一串空了就返回 0。
- 底层机制图解：数组名传参时退化为指向首元素的指针，所以递归靠
a + 1前进一格， 用n - 1表示”还剩几个”。课程原版print_reverse是”先递归、回来时打印“， 因此字符从最后一个开始输出；二分查找每次把区间折半（9 个元素最多 4 层）， 两次递归调用都直接return，属于尾递归。随附的r2c_array_recursion.c实测输出woN/length = 3/sum_tail = 360/find 31 -> index 4/find 60 -> index 7/find 7 -> index -1。 - 作用域与存储期：数组元素本身不在帧里（它们在调用者的帧或堆上）， 递归传递的只是指针；累加器版本（
sum_tail (a+1, n-1, acc + a[0])）把”进度”放进参数， 使帧可以被复用，是尾递归的典型写法。
- 互递归 (Mutual Recursion)：A 调用 B，B 又调用 A。
- 直观解释：两人轮流接话，一句问一句答，直到某句”答完了”为止。
- 底层机制图解：机器层面与普通递归相同，只是调用图成环；必须至少有一处基本情况， 并在使用前前向声明 (forward declaration) 另一个函数，否则编译器解析函数体时不知道它的原型。 例如
static int32_t is_odd (int32_t n); static int32_t is_even (int32_t n) { if (0 == n) { return 1; } return is_odd (n - 1); }，is_odd对称地返回is_even (n - 1)； 实测is_even(4) = 1, is_odd(4) = 0，is_even(10)的递归深度为 11 帧。 - 作用域与存储期：两个函数都用文件作用域
static（否则要在头文件里声明）；深度仍由栈决定。
- 回溯 (Backtracking)：尝试一个候选 → 递归求解剩余问题 → 失败就撤销这次尝试换下一个。
- 直观解释：走迷宫时在岔路口画粉笔记号；走进死胡同就退回最近一个还有未试方向的岔路口。
- 底层机制图解：核心是”修改 → 递归 → 撤销“三步。撤销之所以必要，是因为解的状态通常放在 文件作用域数组（所有层共享）里；标记数组
found同时充当①已访问集合 ②停止条件 ③输出结果。 - 作用域与存储期：共享状态（
found、col[]）必须是 static storage duration 或显式传指针； 只属于单次调用的状态才放帧里。哪些要撤销、哪些要累计，是回溯最容易搞错的地方。
- 分治 (Divide and Conquer)：把问题切成若干同形子问题，分别求解再合并。
- 直观解释：整理扑克牌——分成两摞各自理好，再并成一摞（归并排序）。
- 底层机制图解：汉诺塔的
T(n) = 2T(n-1) + 1解出T(n) = 2^n - 1； 归并排序的T(n) = 2T(n/2) + O(n)解出O(n log n)。前者递归树”窄而深”，后者”宽而浅”，代价天差地别。 汉诺塔的函数体只有三行（hanoi(n-1,from,via,to)→ 搬第 n 个盘子 →hanoi(n-1,via,to,from)）， 递推式直接从”2 次递归 + 1 次搬动”读出。r3_hanoi.c的实测结果为：n = 3时打印出 7 步且moves counted = 7（与2^3 - 1吻合），n = 1, 4, 10, 20分别对应1, 15, 1023, 1048575步。 递归树是完全二叉树：结点总数2^(n+1) - 1 = 15（n=3），而同时存活的栈帧峰值只有n + 1 = 4。 注意n = 64需2^64 - 1 ≈ 1.8 × 10^19步，每秒一亿步也要五千年以上—— 分治能把问题描述得很优雅，却不改变问题本身的难度。 - 作用域与存储期：合并阶段通常需要额外空间（归并的临时数组），多来自堆，须自行管理生命周期。
栈帧链图解（factorial(4) 在 x86-64 上的实测地址）：栈向低地址增长，相邻两帧相距 0x30 = 48 字节。
高地址
0x7ffdcc0b7198 ┌──────────────────────────────┐ ← 帧 #1（depth=1, n=4）
│ local_n = 4 │
│ 保存的返回地址、旧 RBP │
├──────────────────────────────┤
0x7ffdcc0b7168 │ local_n = 3 │ ← 帧 #2（n=3），相距 48 字节
├──────────────────────────────┤
0x7ffdcc0b7138 │ local_n = 2 │ ← 帧 #3（n=2）
├──────────────────────────────┤
0x7ffdcc0b7108 │ local_n = 1 │ ← 帧 #4（n=1）
├──────────────────────────────┤
0x7ffdcc0b70d8 │ local_n = 0 │ ← 帧 #5（n=0，基本情况）
低地址 └──────────────────────────────┘ ← 栈顶：运行时 R6/RSP
LC-3 视角下同一件事（R5 帧指针、R6 栈指针、R7 返回地址；R0–R3 为 caller-saved 的参数/返回值寄存器， R4 是全局数据指针，不要拿 R4–R7 当临时寄存器）：
高地址 ┌──────────────────────┐
│ caller 的栈帧 │
├──────────────────────┤
│ parameters │ ← R5+4, R5+5, ... （由调用者压入）
├──────────────────────┤
│ return value │ ← R5+3 ← 紧贴在第一个参数之下
├──────────────────────┤
│ return address (R7) │ ← R5+2 ┐
├──────────────────────┤ ├ 这三格合称 linkage
│ previous frame ptr │ ← R5+1 ┘
├──────────────────────┤
│ local variables │ ← R5+0, R5-1, ... (R5 指向局部变量底部)
低地址 └──────────────────────┘ ← R6 指向栈顶
务必记准这个顺序：R5+0（及 R5-1, R5-2, …）= 局部变量；R5+1 = 旧帧指针； R5+2 = 返回地址；R5+3 = 返回值；R5+4, R5+5, … = 参数。压栈 = ADD R6, R6, #-1 后 STR。
为什么返回值必须在 R5+3（紧邻参数之下）？ 因为调用者取回返回值后要用一条 ADD R6, R6, #(nparams + 1) 同时弹出参数和返回值（538 讲义的原文是 “Read return value / Pop parameters and return value (destroy the params)”）。 课程真实汇编 translate.asm 的 FIND_ABS 正是这样写的：
FIND_ABS
ADD R6,R6,#-4 ; 4 个位置：3 个 linkage + 1 个局部变量
STR R5,R6,#1 ; 保存旧帧指针 -> R5+1
ADD R5,R6,#0 ; 设置帧指针
STR R7,R5,#2 ; 保存返回地址 -> R5+2
LDR R0,R5,#4 ; 第一个参数 num -> R5+4
STR R0,R5,#0 ; 局部变量 abs_value -> R5+0
STR R0,R5,#3 ; 返回值 -> R5+3
LDR R7,R5,#2 ; 恢复返回地址
LDR R5,R5,#1 ; 恢复旧帧指针
ADD R6,R6,#3 ; 弹出局部变量与 linkage（**返回值槽除外**）
RET
代码示例与底层机制分析
示例 1：factorial(4) 的逐帧轨迹
代码 (C):
/* r1_factorial_frames.c
* 编译： gcc -g -std=c99 -Wall -Werror r1_factorial_frames.c -o r1_factorial_frames */
#include <stdio.h>
#include <stdint.h>
static int32_t depth = 0; /* 只为打印轨迹，不属于算法本身 */
static int32_t
factorial (int32_t n)
{
int32_t local_n = n; /* 每一帧都有自己的这一份 */
int32_t result;
depth++;
printf ("push depth=%d &local_n=%p n=%d\n", depth, (void*)&local_n, (int)n);
if (0 == n) {
result = 1; /* 基本情况 */
} else {
result = n * factorial (n - 1); /* 递归情况 */
}
printf ("pop depth=%d &local_n=%p returns %d\n",
depth, (void*)&local_n, (int)result);
depth--;
return result;
}
int
main (void)
{
printf ("factorial(4) = %d\n", (int)factorial (4));
return 0;
}
真实运行输出:
push depth=1 &local_n=0x7ffdcc0b7198 n=4
push depth=2 &local_n=0x7ffdcc0b7168 n=3
push depth=3 &local_n=0x7ffdcc0b7138 n=2
push depth=4 &local_n=0x7ffdcc0b7108 n=1
push depth=5 &local_n=0x7ffdcc0b70d8 n=0
pop depth=5 &local_n=0x7ffdcc0b70d8 returns 1
pop depth=4 &local_n=0x7ffdcc0b7108 returns 1
pop depth=3 &local_n=0x7ffdcc0b7138 returns 2
pop depth=2 &local_n=0x7ffdcc0b7168 returns 6
pop depth=1 &local_n=0x7ffdcc0b7198 returns 24
factorial(4) = 24
【代码做什么？】 1. main 调用 factorial(4)，第 1 帧把 local_n = 4 放在 0x7ffdcc0b7198。
n != 0走递归情况求factorial(3)；当前帧保持存活挂在那里等待，于是压出第 2 帧。- 重复到
n = 0，共 5 帧，每帧相距 48 字节，地址依次递减。 n = 0走基本情况返回 1——唯一”不再调用自己”的点。- 回退：第 5 帧交出 1，第 4 帧算
1*1=1，第 3 帧算2*1=2，第 2 帧算3*2=6，第 1 帧算4*6=24。
【底层机制透视】 4 次乘法不是往下走时做的，而是回来时做的：n * factorial(n-1) 必须先拿到子调用的返回值， 所以乘法指令位于 CALL 之后。这就是”递归成本 = 帧数”的直接后果：第 1 帧在整个递归期间都不能回收。 48 字节/帧是本机实测值，换编译器或 -O2 都会变。栈默认上限 8 MiB（ulimit -s 可查）， 本机大约能撑 8 MiB / 48 B ≈ 17 万 层——这解释了课程那句”宽搜索适合递归，深搜索容易把栈压垮”。
【内存布局图解】 见前面的帧链图（R6/RSP 始终指向最深的帧）。
【与汇编的对应】
; ---- 调用者：压参数后 JSR —— 这一条指令就是"C 里的递归调用" ----
LDR R0, R5, #0 ; R0 = n（本帧的局部变量在 R5+0）
ADD R1, R0, #-1
ADD R6, R6, #-1
STR R1, R6, #0 ; 压参数 -> 被调用者的 R5+4
JSR FACT ; R7 <- 返回地址；PC <- FACT，压出新的一帧
LDR R2, R6, #0 ; R2 = 返回值（被调用者的 R5+3，紧邻参数之下）
ADD R6, R6, #2 ; 一条指令弹出参数与返回值槽
; ---- FACT 的进入/退出序列（与 translate.asm 的 FIND_ABS 完全同构）----
FACT ADD R6, R6, #-4 ; 3 个 linkage 槽 + 1 个局部变量
STR R5, R6, #1 ; 保存旧帧指针 -> R5+1
ADD R5, R6, #0 ; R5 = 新帧基址（局部变量底部）
STR R7, R5, #2 ; 保存返回地址 -> R5+2
LDR R1, R5, #4 ; R1 = 参数 n -> R5+4
; ... n 为 0 走基本情况，否则再次 JSR FACT ...
STR R1, R5, #0 ; local_n（局部变量）-> R5+0
STR R0, R5, #3 ; 返回值 -> R5+3
FACTD LDR R7, R5, #2 ; 恢复返回地址
LDR R5, R5, #1 ; 恢复旧帧指针
ADD R6, R6, #3 ; 弹出局部变量与 linkage（返回值槽除外）
RET ; PC <- R7
示例 2：朴素 Fibonacci 的指数爆炸
代码 (C):
/* r4_fib_calls.c -- 课程约定：F(0)=1, F(1)=1, F(N)=F(N-1)+F(N-2)
* 编译： gcc -g -std=c99 -Wall -Werror r4_fib_calls.c -o r4_fib_calls */
#include <stdio.h>
#include <stdint.h>
static int64_t calls = 0; /* fib 被进入的次数 */
static int32_t
fib_naive (int32_t n)
{
calls++;
if (0 == n || 1 == n) { return 1; }
return fib_naive (n - 1) + fib_naive (n - 2);
}
static int32_t
fib_iter (int32_t n) /* 迭代版本 */
{
int32_t i = 1, j = 1, k = 1, t;
while (n > k) { t = j; j = j + i; i = t; k++; }
return j;
}
int
main (void)
{
int32_t n;
printf (" n | fib(n) | calls for naive fib\n");
for (n = 1; 25 >= n; n++) {
int32_t f;
calls = 0;
f = fib_naive (n); /* 先调用，把计数定下来 */
printf ("%2d | %11d | %ld\n", (int)n, (int)f, (long)calls);
}
calls = 0;
printf ("\nfib_iter(25) = %d (recursive calls made: %ld)\n",
(int)fib_iter (25), (long)calls);
return 0;
}
⚠️ 为什么必须分成两句写？ 如果写成
printf ("%2d \| %11d \| %ld\n", (int)n, (int)fib_naive (n), (long)calls); /* ❌ */那么这一行里”调用
fib_naive“与”读取calls“这两个实参的求值顺序是未指定的 (unspecified order of evaluation)。GCC 12 会先读calls（此时刚被置 0）再调用fib_naive，于是整张表的calls列全部打印 0——程序照样编译、照样运行、毫无警告， 只是结果是错的。这是一个”逻辑错误”的活标本：编译器抓不到它，只有核对输出才能发现。 凡是”某个函数的副作用会影响同一表达式里另一个实参的值”，都必须拆成独立的语句。
真实运行输出（节选）:
n | fib(n) | calls for naive fib
1 | 1 | 1
2 | 2 | 3
3 | 3 | 5
4 | 5 | 9
5 | 8 | 15
10 | 89 | 177
15 | 987 | 1973
20 | 10946 | 21891
25 | 121393 | 242785
fib_iter(25) = 121393 (recursive calls made: 0)
【代码做什么？】
fib_naive每次进入都把calls加一，把”调用次数”变成可测量的量。n = 0或n = 1返回 1（两个基本情况，也是递归树的叶子）；否则返回fib(n-1) + fib(n-2)， 一次调用分裂成两个孩子。- 主程序对
n = 1..25打印fib(n)与调用次数，最后用迭代版本算fib(25)（调用次数 0）。
【底层机制透视】 课程强调的数字在这里得到实测印证：fib(5) 一共调用 15 次，因为同一个 n 被反复计算：
fib(5) ← 1 个结点
/ \
fib(4) fib(3) ← 2 个
/ \ / \
fib(3) fib(2) fib(2) fib(1) ← 4 个
/ \ / \ / \
fib(2) f(1) f(1) f(0) f(1) f(0) ← 7 个（只展开左半）
/ \
fib(1) fib(0) ← 叶子层
数一数：1 + 2 + 4 + 7 + 1 = 15，其中 fib(3) 被算了 2 次、fib(2) 被算了 3 次。 调用次数满足 C(n) = C(n-1) + C(n-2) + 1，与 Fibonacci 同阶，即 C(n) = Θ(φ^n)，φ = (1+√5)/2 ≈ 1.618。 实测比例印证：C(25)/C(24) = 242785/150049 ≈ 1.618；C(20)/C(15) = 21891/1973 ≈ 11.1 ≈ φ^5 = 11.09。 指数爆炸的根因不是”递归慢”，而是”重复子问题”：迭代版本自底向上算，每个 n 只算一次，于是降到 O(n)； 而栈深度始终只有 O(n)。内存与时间必须分开看。
【内存布局图解】
内存（栈）: O(n) 时间（调用次数）: O(φ^n)
┌──────────────────────────┐
│ 帧1 fib(5) → … → 帧5 fib(1) │ 只有一条根到叶的路径同时存活；
└──────────────────────────┘ 兄弟分支的帧"用完即弹、需要再压"
【与汇编的对应】
; R0 = n；两条 JSR FIB 就是"一次调用分裂成两个孩子"（示意：真实编译器把 n 与中间
; 结果放在 R5+0、R5-1 局部变量里；这里直接借用栈顶，注意每次调用后弹出"参数+返回值"两格）
ADD R1, R0, #0
BRz FIB1 ; n == 0 -> 基本情况
ADD R2, R1, #-1
BRz FIB1 ; n == 1 -> 基本情况
ADD R6, R6, #-1
STR R1, R6, #0 ; n 暂存栈上（两次调用之间还要用）
ADD R6, R6, #-1
ADD R0, R1, #-1
STR R0, R6, #0 ; 压参数 n-1
JSR FIB ; 递归调用 #1
LDR R2, R6, #0 ; R2 = fib(n-1)（返回值在参数正下方）
ADD R6, R6, #2 ; 弹出参数与返回值槽
ADD R6, R6, #-1
STR R2, R6, #0 ; fib(n-1) 也要存起来（R0-R3 是 caller-saved）
LDR R1, R6, #1 ; R1 = n（从栈上取回）
ADD R6, R6, #-1
ADD R0, R1, #-2
STR R0, R6, #0 ; 压参数 n-2
JSR FIB ; 递归调用 #2
LDR R3, R6, #0 ; R3 = fib(n-2)
ADD R6, R6, #2 ; 弹出参数与返回值槽
LDR R2, R6, #0 ; R2 = fib(n-1)
ADD R6, R6, #1 ; 弹掉暂存
ADD R0, R2, R3
FIB1 RET
示例 3：回溯与洪水填充 (flood fill)
代码 (C):
/* r5d_maze_compact.c -- 迷宫用位向量表示：L=1, R=2, U=4, D=8, 出口=16
* 编译： gcc -g -std=c99 -Wall -Werror r5d_maze_compact.c -o r5d_maze_compact */
#include <stdio.h>
#include <stdint.h>
enum { LEFT_WALL = 1, RIGHT_WALL = 2, UPPER_WALL = 4, LOWER_WALL = 8, HAS_EXIT = 16 };
#define W 3
#define H 3
/* maze[x][y]：(2,2) 是出口，但被四面墙围死 */
static uint8_t maze[W][H] = {{5, 9, 9}, {4, 2, 10}, {6, 10, 31}};
static uint8_t found[W][H]; /* 0 = 未到过，1 = 到过（文件作用域，初值全 0）*/
static int32_t saw_exit = 0, calls = 0, depth = 0, max_depth = 0;
static void
can_reach (int32_t x, int32_t y)
{
calls++;
if (++depth > max_depth) { max_depth = depth; }
if (found[x][y]) { /* 停止条件：这一格已经到过 */
depth--;
return;
}
found[x][y] = 1; /* 处理当前结点 */
if (0 == (LEFT_WALL & maze[x][y])) { can_reach (x - 1, y); } /* 子结点 */
if (0 == (RIGHT_WALL & maze[x][y])) { can_reach (x + 1, y); }
if (0 == (UPPER_WALL & maze[x][y])) { can_reach (x, y - 1); }
if (0 == (LOWER_WALL & maze[x][y])) { can_reach (x, y + 1); }
if (0 != (HAS_EXIT & maze[x][y])) { saw_exit = 1; }
depth--;
}
int
main (void)
{
int32_t x, y;
can_reach (0, 0);
printf ("spaces reachable from (0,0) ('#' = reached, '.' = not reached)\n");
for (y = 0; H > y; y++) {
for (x = 0; W > x; x++) { printf ("%c", found[x][y] ? '#' : '.'); }
printf ("\n");
}
printf ("saw_exit = %d\n", (int)saw_exit);
printf ("calls = %d, maximum stack depth = %d frames\n",
(int)calls, (int)max_depth);
return 0;
}
真实运行输出:
spaces reachable from (0,0) ('#' = reached, '.' = not reached)
###
###
##.
saw_exit = 0
calls = 19, maximum stack depth = 8 frames
【代码做什么？】
maze[x][y]的每个字节是位向量：第 0 位左墙、第 1 位右墙、第 2 位上墙、第 3 位下墙、第 4 位出口。maze[0][0] = 5 = 1\|4表示左上角同时有左墙与上墙；maze[2][2] = 31表示出口被四面墙围死。can_reach(x,y)：若found[x][y]非 0 就立刻返回（停止条件），否则标记该格， 再对四个方向中”没有墙”的邻居分别递归。main从 (0,0) 做洪水填充，然后把found打印成#/.图。- 输出显示 8 格可达、右下角 (2,2) 不可达，于是
saw_exit = 0：出口存在，但从起点走不到。
【底层机制透视】 found 数组同时承担三个角色：①已访问集合 ②停止条件 ③输出结果。 课程演示的”没有停止条件会怎样”值得亲自体验：把 if (found[x][y]) return; 注释掉， A → B → A → B … 无限互相调用，栈持续向下生长，最终段错误。随附的 r5b_no_stop_demo.c 就是这种情况，实测退出码 139 (SIGSEGV)，而且第一行 printf 的输出也一并丢失—— 它还在 stdout 缓冲区里，进程没来得及 flush（第 14 讲会再遇到这个现象）。 再注意实测的 calls = 19 与 max_depth = 8：调用次数（时间）与栈深度（空间）是两个不同的量。
【内存布局图解】
static storage duration（进程整个生命周期）
┌──────────────────────────────────────────┐
│ maze[3][3] 9 字节 ← 墙的位向量 │
│ found[3][3] 9 字节 ← 访问标记（初值 0）│
│ saw_exit / calls / depth / max_depth │
└──────────────────────────────────────────┘
栈（向低地址增长，最深 8 层）: 帧#1 can_reach(0,0) → 帧#8 栈顶（R6/RSP）
【与汇编的对应】
; CANREACH(x, y)：R0 = x, R1 = y。帧布局与 538 讲义的 FOO 同构（R5 = R6+1）：
; R5+0 = x、R5-1 = y、R5+1 = 旧帧指针、R5+2 = 返回地址、R5+3 = 返回值、R5+4/+5 = 参数
CANREACH
ADD R6, R6, #-5 ; 3 个 linkage 槽 + 2 个局部变量
STR R5, R6, #2 ; 保存旧帧指针
ADD R5, R6, #1 ; 设置本帧指针（局部变量底部）
STR R7, R5, #2 ; 保存返回地址 -> R5+2
STR R0, R5, #0 ; 局部 x -> R5+0
STR R1, R5, #-1 ; 局部 y -> R5-1
LDR R3, R5, #-1 ; R3 = y
ADD R2, R3, R3
ADD R2, R2, R3 ; R2 = 3y
LDR R3, R5, #0 ; R3 = x
ADD R2, R2, R3 ; R2 = x + y * W（课程强调的展平公式）
LEA R3, FOUND
ADD R3, R3, R2 ; R3 = &found[x][y]
LDR R1, R3, #0 ; R1 = found[x][y]
BRnp CRTEARDOWN ; 非 0 -> 已到过，停止条件成立，直接返回
ADD R1, R1, #1
STR R1, R3, #0 ; found[x][y] = 1（处理当前结点）
LEA R3, MAZE
ADD R3, R3, R2 ; R3 = &maze[x][y]
LDR R1, R3, #0 ; R1 = 位向量
AND R1, R1, #1 ; 取"左墙"位
BRnp SKIP_LEFT ; 有墙 -> 不递归
LDR R0, R5, #-1 ; R0 = y
LDR R1, R5, #0
ADD R1, R1, #-1 ; R1 = x - 1
ADD R6, R6, #-1
STR R0, R6, #0 ; 压 y（先压的在上面 -> 被调用者的 R5+5）
ADD R6, R6, #-1
STR R1, R6, #0 ; 压 x-1（-> 被调用者的 R5+4）
JSR CANREACH ; ← 新帧，递归
ADD R6, R6, #3 ; 一条指令弹出 2 个参数与返回值槽
SKIP_LEFT
; 右、上、下三个方向同理
CRTEARDOWN
LDR R7, R5, #2 ; 恢复返回地址
LDR R5, R5, #1 ; 恢复旧帧指针
ADD R6, R6, #4 ; 弹出 2 个局部变量与 linkage（返回值槽除外）
RET
二维数组 maze[x][y] 在 C 中等价于 *(*(maze + x) + y)，展平偏移为 x + y * W； MP8 的洪水填充文档要求写成 red[x + y * width]，正是这个公式。
常见错误与调试技巧
- 忘记基本情况或基本情况不收敛：现象是卡死或段错误。
can_reach少了if (found[x][y]) return;就会A→B→A→B…无限递归。调试：gdb -tui --args ./prog运行后 Ctrl-C，用bt看栈； 同一函数重复出现几百次就是缺停止条件，bt 20只看前 20 层。 - 参数没有向基本情况靠近：例如把
can_reach(x - 1, y)写成can_reach(x + 1, y)， 或数组递归传a而不是a + 1。调试：在gdb中反复p x/p y观察参数是否单调靠近基本情况； 也可临时加if (depth > 100) { printf("%d %d\n", x, y); abort(); }。 - 返回指向本帧局部变量的指针：
char* f(void){ char buf[10]; return buf; }， 现象是返回的字符串内容随机（帧内存已被后续调用覆盖）。调试：gcc -fsanitize=address -g（本机受ulimit -v限制无法启动 ASan 时改用valgrind --track-origins=yes ./prog， 它会报 “Address … on thread 1’s stack”）。 - 以为写了尾递归就不会爆栈：
a[0] + rec(...)之后还有加法，编译器无法复用帧。 调试：objdump -d ./prog \| awk '/<func>:/,/ret/'看是否存在指向自己的callq； 再用gcc -O2与gcc -O2 -fno-optimize-sibling-calls各编译一次对比运行结果。 - 回溯时忘记撤销状态：
col[row]没还原、found没清理，后续分支看到脏数据。 调试：gdb里watch col[3]，每次变化都会停住，配合bt可看出是哪一层改的、有没有改回来。 - 低估递归深度：深度 10 万 × 48 字节 ≈ 4.8 MB，已吃掉默认 8 MB 栈的一半。 调试：
ulimit -s查看栈上限；gcc -fstack-usage生成.su文件给出静态帧大小； 也可在gdb中打印相邻两层局部变量的地址差，算出真实帧大小。
关键要点
- 递归函数由基本情况与递归情况构成；停止条件不仅要存在，还要保证参数向基本情况收敛。
- 每次递归调用都是一次
JSR加一个新栈帧：递归深度直接等于内存占用， 递归树的结点数等于时间开销，两者必须分开评估。 - 回退 (unwinding) 阶段能做真正的功：
print_reverse靠它反序输出，factorial靠它完成乘法； 语句放在递归调用之前还是之后，决定了算法是自顶向下还是自底向上。 - 尾递归只在编译器做尾调用优化时才省栈（
-O0下与普通递归相同），不能用它来规避栈溢出风险。 - 递归的价值在表达力（回溯、分治、树形结构），不在速度：朴素 Fibonacci 说明 “能递归地写”不等于”应该递归地写”，遇到重叠子问题应改用迭代或记忆化。
思考题（带答案）
问题 1：下面的函数在 n = 5 时输出什么？如果把两个 printf 互换位置，输出如何变化？
static void f (int32_t n)
{
if (0 == n) { printf ("B"); return; }
printf ("a");
f (n - 1);
printf ("b");
}
答案：输出 aaaaaBbbbbb：下行阶段每层打印 a（5 个），基本情况打印 B，回退阶段每层打印 b（5 个）。 这说明递归调用之前的语句属于”下行段”，之后的语句属于”回退段”；互换后 a、b 角色对调，变成 bbbbbBaaaaa。 用 gdb 的 break f 配合 continue 观察调用序列即可验证。
问题 2：为什么 fib(25) 只要 242785 次调用，而 fib(40) 就要上亿次？给出把它降到 O(n) 的最小改动。
答案：调用次数满足 C(n) = C(n-1) + C(n-2) + 1，与 Fibonacci 同阶，故 C(n) = Θ(φ^n)，φ ≈ 1.618。 从 25 到 40 差 15 层，放大倍数约 φ^15 ≈ 1364，于是 242785 × 1364 ≈ 3.3 × 10^8，确实是上亿。 最小改动有两条路：① 改成迭代（保留两个前驱值，O(n) 时间、O(1) 空间）； ② 保留递归但加一张表做记忆化 (memoization)。两者都只消除了”重复子问题”。
问题 3：走迷宫的 can_reach 中，如果把 found 改成局部变量（每帧一份），程序还能正确工作吗？
答案：不能。found 是跨越所有分支共享的已访问集合，必须对所有递归层可见；放进帧里就变成每层一份副本， “已经到过 (x,y)”这一信息无法传给兄弟分支，不同分支会反复访问同一格，最终退化为无限递归。 这说明 storage duration 的选择直接决定算法是否成立：需要跨调用共享的状态要用文件作用域 static 或显式传指针， 只属于单次调用的状态才放帧里。顺带一提，MP8 的洪水填充文档特意提醒”不要使用 static 存储”—— 那里的标记数组由包装函数在堆上分配后传入，这样函数才能被反复调用而不留残留状态。两种做法都对， 关键是清楚状态的生命周期边界。