4.2 递推关系：展开、求和与特征方程

递归算法把大问题交给更小问题，运行成本也因此由较小规模的成本定义。把代码翻译成递推关系时，最重要的不是套公式，而是数清子问题数量、规模和当前层工作量。

数列递推与成本递推

数列递推定义值：

Fₙ=Fₙ₋₁+Fₙ₋₂

算法成本递推描述运行资源：

T(n)=T(n-1)+Θ(1)

两者使用相同的数学工具，但不要把函数返回值递推与时间递推混为一谈。一个计算 Fibonacci 的迭代算法，值仍满足 Fibonacci 递推，在单位成本加法模型下，时间却是 Θ(n)。

从代码建立递推

以下 Java 方法要求 a!=null、0≤n≤a.length，读取期间数组不变，且每个前缀和都能用 long 表示。它用于分析递归成本；较大的 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)

这里把每步成本写成同一个正常数 c，是为了展示精确展开。原来的 Θ(1) 只要求各步成本有统一正常数上下界，也能推出线性总成本。固定的正常数基础成本不改变本例的渐近阶，但仍需写入递推定义。

展开与望远镜求和

递推：

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)

于是问题转化为估计求和。

以下求和下标均为 i=1,...,n：

Σ 1 = Θ(n)
Σ i = Θ(n²)
Σ i² = Θ(n³)
Σ 1/i = Θ(log n)

代入法不是“展开几层猜答案”

代入法通常分两步：

1. 由展开、递归树或经验猜出界；
2. 用归纳法证明这个界。

例：

T(n)=T(⌊n/2⌋)+1

猜测 T(n)=O(log n)。证明时要找到常数 c,n₀，使：

T(n)≤c log₂ n + d

并处理基础范围与取整。渐近证明不能只写“连续除以 2，所以显然”。

把定义补成 T(1)=d，递推用于整数 n≥2，就有精确解 T(n)=d+⌊log₂n⌋。当 n≥2 时，⌊log₂⌊n/2⌋⌋=⌊log₂n⌋−1，代入归纳假设恰好恢复该式；n=1 单独满足初值。下面用 Python 3 整数除法计数，避开浮点对数的取整误差：

def halvings(n):
    if n < 1:
        raise ValueError("positive integer required")
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps

print([halvings(n) for n in [1, 2, 3, 4, 7, 8]])  # [0, 1, 1, 2, 2, 3]

递归树按层累加成本

先设 n=2^k、T(1)=Θ(1)，归并排序递推为：

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ⁿ；若有非齐次项，还需寻找特解。

例如给定 a₀=2,a₁=3，由 A+B=2,A+2B=3 得 A=B=1，所以 aₙ=1+2ⁿ。下面独立生成递推值，再与闭式逐项比较：

values = [2, 3]
for n in range(2, 9):
    values.append(3 * values[-1] - 2 * values[-2])
assert values == [1 + 2**n for n in range(9)]
print(values[:5])  # [2, 3, 5, 9, 17]

这种方法适合常系数线性递推，不适用于任意递推。

Fibonacci 的增长率

Fibonacci 特征方程：

r²=r+1

根为：

φ=(1+√5)/2
ψ=(1-√5)/2

序列有 Binet 公式：

Fₙ=(φⁿ-ψⁿ)/√5

因为 |ψ|<1，Fₙ=Θ(φⁿ)。

该公式在实数数学中精确成立；直接用浮点 φⁿ 再取整并不是任意大 n 的可靠整数算法，误差会随幂运算放大。

朴素递归函数的调用成本满足近似：

C(n)=C(n-1)+C(n-2)+Θ(1)

在单位成本算术模型下，朴素算法因此是 Θ(φⁿ)，O(2ⁿ) 是较松上界。只数函数调用时，C(0)=C(1)=1 且 C(n)=C(n-1)+C(n-2)+1，可归纳得 C(n)=2Fₙ₊₁−1。这个非负整数输入的小例子会返回数值与调用数：

def fib_with_calls(n):
    if n < 2:
        return n, 1
    a, ca = fib_with_calls(n - 1)
    b, cb = fib_with_calls(n - 2)
    return a + b, 1 + ca + cb

print(fib_with_calls(10))  # (55, 177)

记忆化后，每个下标只展开一次，算术次数和缓存条目数均为 Θ(n)；递归栈深度仍为 Θ(n)。迭代只需常数个大整数变量，但不能因此把存储位数也说成常数。

别忘了调用栈与数值成本

只数递归调用可能遗漏：

• 每层复制切片的成本；
• 大整数加法随位数增长，不再是常数时间；
• 递归深度带来的栈空间；
• 哈希缓存键的计算；
• I/O、锁和内存分配。

Fibonacci 数本身位数随 n 线性增长，所以在任意精度整数模型下，即使算法只做 n 次加法，位运算成本也不能永远视为常数。

若按常见线性位成本大整数加法计，迭代的总加法成本为 Θ(1+2+...+n)=Θ(n²)，工作整数占 Θ(n) 位；缓存全部前 n 项则占 Θ(n²) 数值位。这些是位模型下的界，不包含对象头等运行时开销。

完成检查

1. 展开 T(n)=T(n-1)+2n；
2. 用递归树求 T(n)=3T(n/3)+n；
3. 用特征方程解 aₙ=5aₙ₋₁-6aₙ₋₂；
4. 分别写出朴素 Fibonacci 的值递推和调用成本递推；
5. 为记忆化版本列出时间、缓存空间和调用栈空间。

参考资料

• MIT Mathematics for Computer Science