元数据卡
- 前置知识：第3章 证明方法（归纳法）
- 预计时间：45 分钟
- 核心难度：进阶
- 完成标志：能够写递归函数的数学定义，区分递推与递归，解简单的递推关系
你的进度
前三层教会了你逻辑、集合和证明。第四层的石门是用镜子做的——往里面看，墙上挂的画里还挂着一幅同样的画。
你的任务
你写过一个递归函数——它调自己。但为什么它能终止？怎么分析它的时间复杂度？"递归"很多时候被当作"编程技巧"教，但它的数学根源比编程早几千年。这一章让你从数学上理解递归的本质——递推关系及其求解方法。
本章分层
- 必读：递归定义，递推关系，主定理
- 选读：生成函数法
破局 · 溯源
你实现了一个二分搜索，写了一个斐波那契数列的函数。运行测试，通过。但面试官问："时间复杂度是多少？"你开始套公式：T(n) = T(n/2) + O(1) 是 O(log n)，T(n) = T(n-1) + T(n-2) 是 O(2ⁿ)。这些公式来自哪里？为什么能用？
递归定义：用自身来定义自己。三个要素：
- 基本情况：最简单的实例，直接给出结果。
- 递归规则：如何从较小实例构造当前实例。
- 终止性：每次递归调用必须缩小问题的规模，最终触及基本情况。
数学上的递归定义，比如斐波那契数列：
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (n ≥ 2)递推关系则是递归算法的时间/空间复杂度的数学描述。二分搜索的递推关系：
T(1) = 1
T(n) = T(n/2) + 1 (每次将问题规模减半，加一次比较)求解这个递推关系：连续代入。
T(n) = T(n/2) + 1
= (T(n/4) + 1) + 1 = T(n/4) + 2
= (T(n/8) + 1) + 2 = T(n/8) + 3
= ...
= T(1) + log₂(n)
= 1 + log₂(n)
= O(log n)更一般地，对于形如 T(n) = aT(n/b) + f(n) 的递推（分治算法），有主定理：
给定 T(n) = aT(n/b) + f(n)，其中 a ≥ 1, b > 1：
- 如果 f(n) = O(n^{log_b(a) - ε})，则 T(n) = Θ(n^{log_b(a)})
- 如果 f(n) = Θ(n^{log_b(a)}), 则 T(n) = Θ(n^{log_b(a)} log n)
- 如果 f(n) = Ω(n^{log_b(a) + ε})，且满足正则条件 a f(n/b) ≤ c f(n)，则 T(n) = Θ(f(n))
不要被符号吓住。实际使用场景：
- 二分搜索：a=1, b=2, f(n)=1。log_b(a)=log₂(1)=0，f(n)=Θ(1)=Θ(n⁰) → 情况2，T(n)=Θ(log n)
- 归并排序：a=2, b=2, f(n)=n。log_b(a)=1，f(n)=Θ(n¹) → 情况2，T(n)=Θ(n log n)
- 暴力斐波那契（递归）：a=2, b=1 不适用——这个不是分治，是线性递归。
递归与迭代的关系值得注意。任何递归算法都可以转换为等价的迭代版本（用显式栈）。反过来不一定——不是所有迭代都能自然地写成递归。递归强调"是什么"（声明性），迭代强调"怎么做"（过程式）。
斐波那契的递归实现（指数时间）和迭代实现（线性时间）是同一个数学定义的不同计算路径。数学定义了"是什么"，算法决定了"怎么算"。
常见陷阱
- 忽略基本情况。没有基本情况的递归是无限循环。
- 认为递归总是比迭代慢。递归的优势在表达力上——树遍历、图搜索、回溯等场景的递归代码比迭代版本更容易正确。
- 用主定理套不属于分治模式的递推。例如 T(n) = T(n-1) + n 不是 aT(n/b) + f(n) 形式，需要用代入法或递归树求解。
通关挑战
- 写出阶乘 n! 的递归定义，并用代入法求其递推 T(n) = T(n-1) + 1 的时间复杂度。
- 写出归并排序的递推关系并用主定理求解。
- 实现斐波那契数列的三个版本：朴素递归、带记忆化递归、迭代。对比各版本的时间复杂度。
旅人笔记
递归是数学和编程的交叉路口。递推关系告诉你"多快"，递归定义告诉你"是什么"。主定理是解决分治算法递推的快捷方式。
→ 下一站预告：递归帮助你在单个问题内部处理自引用。但如果你想描述"两个事物之间的关系"或"一个输入到一个输出的映射"，你需要关系和函数。