4.2 递推关系：展开、求和与特征方程
阿花把递归程序的每一层成本记到账本上，接下来要把层层依赖化成可以求解的递推关系。
递归算法把大问题交给更小问题，运行成本也因此由较小规模的成本定义。把代码翻译成递推关系时，最重要的不是套公式，而是数清子问题数量、规模和当前层工作量。
数列递推与成本递推
数列递推定义值：
Fₙ=Fₙ₋₁+Fₙ₋₂算法成本递推描述运行资源：
T(n)=T(n-1)+Θ(1)两者使用相同的数学工具，但不要把函数返回值递推与时间递推混为一谈。一个计算 Fibonacci 的迭代算法，值仍满足 Fibonacci 递推，时间却是 Θ(n)。
从代码建立递推
long sum(long[] a, int n) {
if (n == 0) return 0;
return sum(a, n - 1) + a[n - 1];
}若数组访问和加法视为常数时间：
T(0)=Θ(1)
T(n)=T(n-1)+Θ(1)展开：
T(n)=T(n-1)+c
=T(n-2)+2c
=...
=T(0)+nc
=Θ(n)基础成本不能决定渐近阶，但它是精确递推定义的一部分。
展开与望远镜求和
递推：
T(n)=T(n-1)+n, T(0)=c展开：
T(n)=c+1+2+...+n
=c+n(n+1)/2
=Θ(n²)更一般地：
T(n)-T(n-1)=g(n)从 1 到 n 求和，左边中间项相消：
T(n)-T(0)=Σ_{i=1..n} g(i)于是问题转化为估计求和。
常用量级：
Σ 1 = Θ(n)
Σ i = Θ(n²)
Σ i² = Θ(n³)
Σ 1/i = Θ(log n)代入法不是“展开几层猜答案”
代入法通常分两步：
- 由展开、递归树或经验猜出界；
- 用归纳法证明这个界。
例：
T(n)=T(⌊n/2⌋)+1猜测 T(n)=O(log n)。证明时要找到常数 c,n₀，使：
T(n)≤c log₂ n + d并处理基础范围与取整。渐近证明不能只写“连续除以 2，所以显然”。
递归树按层累加成本
归并排序：
T(n)=2T(n/2)+cn递归树：
第 0 层：1 个问题，每个合并成本 cn -> cn
第 1 层：2 个 n/2，合计 -> cn
第 2 层：4 个 n/4，合计 -> cn
...
共 log₂n 层总内部成本 cn log₂n，叶子总成本 Θ(n)，所以：
T(n)=Θ(n log n)递归树也能帮助发现子问题不等大、层成本变化等情况，但画图仍需转成上下界论证。
线性齐次递推与特征方程
数列：
aₙ=3aₙ₋₁-2aₙ₋₂尝试解 aₙ=rⁿ：
r²=3r-2
r²-3r+2=0
(r-1)(r-2)=0两个不同根 1,2 给出通解：
aₙ=A·1ⁿ+B·2ⁿ再用初始值解 A,B。若根重复，解中会出现 n rⁿ；若有非齐次项，还需寻找特解。
这种方法适合常系数线性递推，不适用于任意递推。
Fibonacci 的增长率
Fibonacci 特征方程：
r²=r+1根为：
φ=(1+√5)/2
ψ=(1-√5)/2序列有 Binet 公式：
Fₙ=(φⁿ-ψⁿ)/√5因为 |ψ|<1，Fₙ=Θ(φⁿ)。
朴素递归函数的调用成本满足近似：
C(n)=C(n-1)+C(n-2)+Θ(1)所以也是 Θ(φⁿ)，常见的 O(2ⁿ) 只是较松上界。加入记忆化后，每个 n 只计算一次，时间 Θ(n)、缓存空间 Θ(n)；迭代可把额外状态缩到常数个数。
别忘了调用栈与数值成本
只数递归调用可能遗漏：
- 每层复制切片的成本；
- 大整数加法随位数增长，不再是常数时间；
- 递归深度带来的栈空间；
- 哈希缓存键的计算；
- I/O、锁和内存分配。
Fibonacci 数本身位数随 n 线性增长，所以在任意精度整数模型下，即使算法只做 n 次加法，位运算成本也不能永远视为常数。
完成检查
- 展开
T(n)=T(n-1)+2n； - 用递归树求
T(n)=3T(n/3)+n； - 用特征方程解
aₙ=5aₙ₋₁-6aₙ₋₂； - 分别写出朴素 Fibonacci 的值递推和调用成本递推；
- 为记忆化版本列出时间、缓存空间和调用栈空间。