递归与数学归纳法

作者收录于类别算法

2026-08-04 2026-08-04 约 1844 字预计阅读 4 分钟

这篇笔记怎么来的 学 Q206 反转链表的递归解法时，卡在"假设小问题正确，当前这步对不对"这句话上。这篇把当时的对话整理成复习材料：这句话到底什么意思、为什么不是循环论证、以及数学归纳法如何给递归兜底。

1 先解决那句话：“假设小问题正确，当前这步对不对”

1.1 为什么这句话让人懵

因为它听起来像"先假设结论是对的，再去验证结论"——像循环论证。但实际上它假设的不是你要证明的那个问题，而是比它小一号的问题。

1.2 这句话的真实含义

它是一条"如果……那么……“的检查：

如果 reverseList(2→3→4) 已经正确返回 4→3→2（规模 $n-1$），那么我接下来这一步（让 2 指回 1、断开 1→2）做完后，1→2→3→4 是不是就变成正确的 4→3→2→1（规模 $n$）？

注意：小问题比大问题短一截，而最短的那个（空链表或单节点）是直接返回的，不需要假设。所以这条"如果……那么……“链有真正的起点，不会循环。

1.3 用斐波那契把这句话坐实

假设小问题正确：如果 fib(3)=2、fib(4)=3，那么 fib(5)=fib(4)+fib(3)=5，对不对？ 这就是一句加法，可以拿具体数字验证，没有玄学。

而 fib(3)、fib(4) 又各自依赖更小的 fib(1)=1、fib(2)=1——它们是基例，写在定义里，不需要假设。链条从基例一路推到目标，长度有限。

1.4 为什么"跳进栈里逐个看"也是对的

直接跳进调用栈一层层看，确实是对的——那相当于把这条"如果……那么……“链完整展开了。归纳法只是把这个展开压缩成两步检查，不用每次为不同输入重跳一遍栈：

链条的第一环成立（基例）
任意一环倒下会推倒下一环（归纳步）

两个都确认过，整条链就永远成立。跳栈是"展开验证”，归纳是"压缩验证”，结果一样。

2 我自己的判断 SOP（这次对话的收获）

用我自己的话说
拆出小问题，假设它已经被处理好了。例：1→2→3→4→5 的小问题是 2→3→4→5，假设它已经变成 5→4→3→2。
问自己：我只做"一步”（把 1 接到末尾），能不能得到 5→4→3→2→1？
这一步能实现 → 整个递归就可实现。

用 1→2→3→4 走一遍：

1
2
3
小问题 2→3→4，假设已变成 4→3→2
一步 = 让 2->next = 1（并断开 1->next）
结果 4→3→2→1 ✓

别忘了补上基例检查 上面的 SOP 只检查了"归纳步"。还差一步：最小的问题（空链表/单节点）直接给答案，不需要假设。两步合起来才是完整的归纳法：
最小问题直接成立（基例）
假设小问题成立，一步能推出大问题成立（归纳步）

3 数学归纳法两步

基例：第 1 个成立。
归纳步：假设第 $k$ 个成立，推出第 $k+1$ 个成立。

多米诺类比：确认第一块会倒 + 确认任意一块倒下会撞倒下一块 → 全部会倒。不需要看完全部骨牌。

归纳假设不是白拿的 “假设第 $k$ 个成立"不是免费午餐：它最终锚定在基例上，而且每次只向前推一步。这就是它和"循环论证"的本质区别。

4 递归代码 = 把归纳定义翻译成代码

斐波那契的定义本身就是归纳的：

1
2
3
F(1) = 1                        （基例）
F(2) = 1                        （基例）
F(n) = F(n-1) + F(n-2)          （归纳步，n ≥ 3）

1
2
3
4
int fib(int n) {
    if (n == 1 || n == 2) return 1;      // 基例
    return fib(n - 1) + fib(n - 2);      // 归纳步
}

用归纳法证明"前 $n$ 项和 = $F(n+2) - 1$"：

$n=1$：和 $=1$，$F(3)-1=1$ ✓
假设 $n=k$ 成立：$sum(k)=F(k+2)-1$，则 $sum(k+1)=F(k+2)-1+F(k+1)=F(k+3)-1$ ✓

5 两种递归写法（以反转链表为例）

经典版 reverseList(head)：递归到最深处，回溯时做 head->next->next = head。不是尾递归。
双指针改递归 reverse(pre, cur)：状态全在参数里，递归调用是最后一句（尾递归），展开就是 while 循环。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
ListNode* reverse(ListNode* pre, ListNode* cur) {
    if (cur == nullptr) return pre;      // 循环退出条件
    ListNode* temp = cur->next;          // 保存下一个，防止断链
    cur->next = pre;                     // 反转当前指针
    return reverse(cur, temp);           // 相当于 pre = cur; cur = temp;
}

ListNode* reverseList(ListNode* head) {
    return reverse(nullptr, head);       // 相当于 pre = nullptr; cur = head;
}

展开：reverse(NULL,1) → reverse(1,2) → reverse(2,3) → reverse(3,4) → reverse(4,NULL)，和循环逐轮等价。

6 自测

能说清"假设小问题正确"为什么不是循环论证
能用具体数字验证 fib(5) 的"如果……那么……”
用自己的 SOP 讲一遍：拆小问题 → 假设处理完 → 只做一步 → 判断能否得到答案
能把迭代版机械改写成尾递归版
能讲出归纳法的两步和多米诺类比

目录