递归与分治

第二十四章：递归与分治

你写下一个函数，它的函数体里调用了自己。程序没有陷入死循环——因为每次调用时问题规模缩小了一点，直到触底返回。这就是递归：一种把复杂问题拆解为相同结构的更小问题的思维方式。

递归不是语法糖，不是编程技巧，而是一种计算模型。Church 和 Turing 在 1936 年分别用 λ-演算和图灵机证明了可计算性的等价——而 λ-演算的核心机制就是递归定义。你在 Python 中写下 def f(n): return f(n-1) 时，你使用的是与数学归纳法同构的推理结构：假设 f(n-1) 已经正确，证明 f(n) 也正确。

分治（Divide and Conquer）是递归的一种特殊应用模式：把问题分成若干规模更小的子问题，递归求解，然后将子问题的解合并成原问题的解。归并排序、快速幂、Karatsuba 大整数乘法、Strassen 矩阵乘法——这些看似不相关的算法，背后都是同一个分治框架。

本章将从递归的三要素出发，深入到分治的数学分析，最后落地到面试中的高频应用题。你将看到：递归不只是"函数调用自己"，分治不只是"把数组分成两半"。它们是算法设计中最强大的思维范式之一。

Level 1 · 你需要知道的

1.1 递归的三要素

每一个正确的递归函数必须包含三个要素：

这三个要素对应数学归纳法的三个部分：基础步（base step）、归纳步（inductive step）、良序性（well-ordering）。

为什么是这三个而不是别的？ 因为递归的本质是在良基关系（well-founded relation）上的归纳。良基关系要求不存在无限下降链——这正是"规模必须缩小"的数学表达。没有基础情况，递归没有终点；没有递推关系，递归没有计算内容；没有规模缩小，递归不终止。这三个条件恰好是递归终止且正确的充要条件（Floyd, "Assigning Meanings to Programs", 1967）。

阶乘：递归的 Hello World

def factorial(n: int) -> int:
    """计算 n! = n × (n-1) × ... × 1
    
    三要素分析:
    - 基础情况: n == 0 时返回 1（0! = 1 是数学定义）
    - 递推关系: n! = n × (n-1)!
    - 规模缩小: n → n-1，严格递减，必然到达 0
    """
    if n == 0:          # 基础情况
        return 1
    return n * factorial(n - 1)  # 递推 + 规模缩小

执行 factorial(4) 的过程：

factorial(4)
  = 4 * factorial(3)
  = 4 * (3 * factorial(2))
  = 4 * (3 * (2 * factorial(1)))
  = 4 * (3 * (2 * (1 * factorial(0))))
  = 4 * (3 * (2 * (1 * 1)))
  = 4 * (3 * (2 * 1))
  = 4 * (3 * 2)
  = 4 * 6
  = 24

注意这个展开过程的形状：先向右展开（递归调用），再从右向左收缩（返回值回传）。这就是递归的"递"和"归"——先递推到基础情况，再逐层归回结果。

斐波那契数列：递归 vs 迭代

def fib_recursive(n: int) -> int:
    """朴素递归实现 Fibonacci
    
    三要素:
    - 基础情况: n <= 1 时返回 n
    - 递推关系: F(n) = F(n-1) + F(n-2)
    - 规模缩小: n → n-1 和 n → n-2
    
    问题: 时间复杂度 O(2^n)，因为存在大量重复计算
    """
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)


def fib_iterative(n: int) -> int:
    """迭代实现 Fibonacci — O(n) 时间，O(1) 空间"""
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

为什么递归版本慢？ 画出 fib_recursive(5) 的调用树：

                    fib(5)
                   /      \
              fib(4)      fib(3)
             /    \       /    \
         fib(3)  fib(2) fib(2) fib(1)
        /    \   /   \   /   \
    fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
    /   \
fib(1) fib(0)

fib(3) 被计算了 2 次，fib(2) 被计算了 3 次。对于 fib(n)，总调用次数约为 φⁿ ≈ 1.618ⁿ（其中 φ 是黄金比例），因此时间复杂度是指数级的。迭代版本每个子问题只计算一次，所以是 O(n)。

递归 vs 迭代的一般比较：

结论：递归不是"更高级"的写法，迭代也不是"更低级"的写法。选择哪个取决于问题结构是否天然递归。 斐波那契是线性递推，用迭代更自然；树的遍历是递归结构，用递归更自然。

1.2 分治的核心思想

分治算法遵循三步范式：

Divide-and-Conquer(P):
    1. DIVIDE: 将问题 P 分解为 k 个子问题 P₁, P₂, ..., Pₖ
    2. CONQUER: 递归求解每个子问题
    3. COMBINE: 将子问题的解合并为原问题的解

这个范式最早被 Knuth 在 The Art of Computer Programming (1973) 中系统阐述，但思想可以追溯到更早。任何分治算法都必须回答三个设计问题：

1. 怎么分？ —— 如何将问题划分为子问题
2. 什么时候停？ —— 子问题多小时直接求解
3. 怎么合？ —— 如何将子问题的解组合起来

分治有效的前提条件：

• 子问题与原问题结构相同（自相似性）
• 子问题之间互不重叠（否则应该用动态规划）
• 合并步骤的代价不能太大（否则分治没有收益）

1.3 归并排序：分治的经典实现

归并排序是分治思想的教科书级实现。John von Neumann 在 1945 年首次描述了这一算法（Knuth, TAOCP Vol. 3, 1973）。

def merge_sort(arr: list) -> list:
    """归并排序 — O(n log n) 时间，O(n) 空间
    
    分治三步:
    1. DIVIDE: 从中间切开，分成左右两半
    2. CONQUER: 递归排序左半和右半
    3. COMBINE: 合并两个有序数组
    """
    n = len(arr)
    if n <= 1:  # 基础情况：0或1个元素已有序
        return arr
    
    mid = n // 2
    left = merge_sort(arr[:mid])      # 递归排左半
    right = merge_sort(arr[mid:])     # 递归排右半
    return merge(left, right)         # 合并


def merge(left: list, right: list) -> list:
    """合并两个有序数组为一个有序数组 — O(n)"""
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= 保证稳定性
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # 将剩余元素追加
    result.extend(left[i:])
    result.extend(right[j:])
    return result

时间复杂度分析：

设 T(n) 为归并排序 n 个元素的时间：

• 分解：O(1)（只是计算中点）
• 递归：2 × T(n/2)（两个规模为 n/2 的子问题）
• 合并：O(n)（线性扫描两个有序数组）

递推关系：T(n) = 2T(n/2) + O(n)

由主定理（Master Theorem）：a=2, b=2, f(n)=O(n)，log_b(a) = 1，f(n) = Θ(n^1)，属于 Case 2，因此 T(n) = O(n log n)。

为什么归并排序的空间复杂度是 O(n)？ 合并步骤需要额外的数组来存放结果。虽然递归深度是 O(log n)，但在每一层合并时需要 O(n) 的临时空间（所有层共享），因此总空间是 O(n)。

1.4 快速幂：O(log n) 计算 a^n

计算 a^n 的朴素方法是连乘 n 次，时间 O(n)。当 n = 10⁹ 时，这需要 10⁹ 次乘法。快速幂（也叫 Binary Exponentiation 或 Exponentiation by Squaring）利用分治将其降到 O(log n)。

核心思想：

$$a^n = \begin{cases} 1 & \text{if } n = 0 \ (a^{n/2})^2 & \text{if } n \text{ is even} \ a \cdot (a^{(n-1)/2})^2 & \text{if } n \text{ is odd} \end{cases}$$

每次递归将指数减半，所以只需要 O(log n) 次乘法。

def power_recursive(a: float, n: int) -> float:
    """快速幂 — 递归版本
    
    分治三步:
    1. DIVIDE: 将 a^n 分解为 a^(n/2) 的子问题
    2. CONQUER: 递归计算 a^(n/2)
    3. COMBINE: 平方（偶数情况）或 平方再乘 a（奇数情况）
    """
    if n == 0:
        return 1
    if n < 0:
        return 1.0 / power_recursive(a, -n)
    
    half = power_recursive(a, n // 2)
    if n % 2 == 0:
        return half * half
    else:
        return half * half * a


def power_iterative(a: float, n: int) -> float:
    """快速幂 — 迭代版本（更常用）
    
    思路: 将 n 表示为二进制，从低位到高位处理
    例如 a^13 = a^(1101₂) = a^8 × a^4 × a^1
    """
    if n < 0:
        a = 1.0 / a
        n = -n
    
    result = 1
    base = a
    while n > 0:
        if n & 1:          # 当前二进制位为 1
            result *= base
        base *= base       # base 依次为 a, a², a⁴, a⁸, ...
        n >>= 1           # 右移一位
    return result

快速幂的应用场景：

• 大数模幂：pow(a, n, mod) — Python 内置就用这个算法
• RSA 加密的核心运算
• 矩阵快速幂：用于加速线性递推（如 O(log n) 计算斐波那契）
• 竞赛中的常见操作

def matrix_power(M: list, n: int, mod: int) -> list:
    """矩阵快速幂 — 用于加速线性递推"""
    size = len(M)
    # 单位矩阵
    result = [[1 if i == j else 0 for j in range(size)] for i in range(size)]
    
    while n > 0:
        if n & 1:
            result = matrix_multiply(result, M, mod)
        M = matrix_multiply(M, M, mod)
        n >>= 1
    return result


def matrix_multiply(A: list, B: list, mod: int) -> list:
    """矩阵乘法（取模）"""
    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod
    return C


def fib_fast(n: int, mod: int = 10**9 + 7) -> int:
    """O(log n) 计算第 n 个 Fibonacci 数
    
    利用: [F(n+1), F(n)] = [[1,1],[1,0]]^n × [1, 0]
    """
    if n <= 1:
        return n
    M = [[1, 1], [1, 0]]
    result = matrix_power(M, n, mod)
    return result[0][1]

1.5 常见错误与修复

错误 1：忘记基础情况

# 错误：无限递归
def bad_sum(arr, i=0):
    return arr[i] + bad_sum(arr, i + 1)

# 修复：添加基础情况
def good_sum(arr, i=0):
    if i == len(arr):  # 基础情况
        return 0
    return arr[i] + good_sum(arr, i + 1)

错误 2：规模没有缩小

# 错误：n 没有变化
def bad_power(a, n):
    if n == 0:
        return 1
    return a * bad_power(a, n)  # 应该是 n-1

# 修复
def good_power(a, n):
    if n == 0:
        return 1
    return a * good_power(a, n - 1)  # 规模缩小

错误 3：基础情况不完整

# 错误：只处理了 n==0，没处理 n==1
def bad_fib(n):
    if n == 0:
        return 0
    return bad_fib(n - 1) + bad_fib(n - 2)  # n=1 时调用 fib(-1)

# 修复：覆盖所有基础情况
def good_fib(n):
    if n <= 1:  # 同时处理 n=0 和 n=1
        return n
    return good_fib(n - 1) + good_fib(n - 2)

Level 2 · 它是怎么运行的

2.1 递归的执行过程：调用栈可视化

要真正理解递归，必须理解它在计算机中的执行机制。每次函数调用会在调用栈（Call Stack）上创建一个新的栈帧（Stack Frame），包含：

• 函数的局部变量
• 参数值
• 返回地址（调用完成后回到哪里继续执行）

import sys

def factorial_traced(n: int, depth: int = 0) -> int:
    """带可视化的阶乘递归"""
    indent = "  " * depth
    print(f"{indent}factorial({n}) called")
    
    if n == 0:
        print(f"{indent}factorial({n}) returns 1")
        return 1
    
    result = n * factorial_traced(n - 1, depth + 1)
    print(f"{indent}factorial({n}) returns {result}")
    return result

# factorial_traced(4) 的输出:
# factorial(4) called
#   factorial(3) called
#     factorial(2) called
#       factorial(1) called
#         factorial(0) called
#         factorial(0) returns 1
#       factorial(1) returns 1
#     factorial(2) returns 2
#   factorial(3) returns 6
# factorial(4) returns 24

调用栈在内存中的样子：

当执行到 factorial(0) 时，栈中有 5 个栈帧:

┌─────────────────────────┐  ← 栈顶 (Stack Top)
│ factorial(0)            │
│   n = 0                 │
│   return addr → line X  │
├─────────────────────────┤
│ factorial(1)            │
│   n = 1                 │
│   return addr → line X  │
├─────────────────────────┤
│ factorial(2)            │
│   n = 2                 │
│   return addr → line X  │
├─────────────────────────┤
│ factorial(3)            │
│   n = 3                 │
│   return addr → line X  │
├─────────────────────────┤
│ factorial(4)            │
│   n = 4                 │
│   return addr → main    │
└─────────────────────────┘  ← 栈底 (Stack Bottom)

每次递归调用 push 一个栈帧，每次返回 pop 一个。栈的最大深度等于递归的最大深度。对于 factorial(n)，最大深度是 n+1；对于二分递归（如归并排序），最大深度是 O(log n)。

关键洞察：递归深度 ≠ 总调用次数。 归并排序 n 个元素有 O(n log n) 次操作，但递归深度只有 O(log n)。这意味着栈空间消耗远小于时间消耗。

2.2 尾递归优化

尾递归（Tail Recursion） 是指递归调用是函数的最后一个操作，调用之后不需要对返回值做任何计算。

# 非尾递归：返回后还要乘以 n
def factorial_normal(n):
    if n == 0:
        return 1
    return n * factorial_normal(n - 1)  # 乘法在递归调用之后

# 尾递归：递归调用是最后的操作
def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)  # 最后一步就是递归调用

为什么尾递归可以优化？ 因为当递归调用是最后的操作时，当前栈帧在调用之后就不再需要了——它的唯一作用是接收返回值并原样传递给上一层。所以编译器可以直接复用当前栈帧，将尾递归转换为循环，从 O(n) 空间降到 O(1) 空间。

支持尾递归优化（Tail Call Optimization, TCO）的语言：

• Scheme：规范强制要求 TCO（R5RS, 1998）
• Haskell：惰性求值 + TCO
• Scala：@tailrec 注解保证
• C/C++：GCC/Clang 在 -O2 下会做

Python 不支持尾递归优化。 Guido van Rossum 在 2009 年明确表示不会加入这一特性，理由是：

1. 会破坏 stack trace，让调试变困难
2. Python 的设计哲学是"显式优于隐式"

这意味着在 Python 中，即使你写成尾递归形式，它依然会消耗 O(n) 的栈空间。如果关心栈深度，必须手动转为迭代。

2.3 Karatsuba 大整数乘法

两个 n 位数相乘，小学方法需要 O(n²) 次个位数乘法。1960 年，年仅 23 岁的苏联数学家 Anatoly Karatsuba 发现了一个 O(n^1.585) 的分治方法，推翻了 Kolmogorov 关于乘法下界为 Ω(n²) 的猜想。

核心思想： 将 n 位数拆成高半部分和低半部分。

设 x = x_H · B^m + x_L，y = y_H · B^m + y_L，其中 B 是进制基数，m = n/2。

朴素方法： x · y = x_H·y_H · B^2m + (x_H·y_L + x_L·y_H) · B^m + x_L·y_L

需要 4 次 n/2 位乘法。递推关系 T(n) = 4T(n/2) + O(n)，解为 T(n) = O(n²) —— 没有改进。

Karatsuba 的天才观察： 只需要 3 次乘法！

定义：

• z₂ = x_H · y_H
• z₀ = x_L · y_L
• z₁ = (x_H + x_L) · (y_H + y_L) - z₂ - z₀

那么 x · y = z₂ · B^2m + z₁ · B^m + z₀

验证：z₁ = x_H·y_H + x_H·y_L + x_L·y_H + x_L·y_L - x_H·y_H - x_L·y_L = x_H·y_L + x_L·y_H ✓

递推关系变为 T(n) = 3T(n/2) + O(n)，由主定理：log₂3 ≈ 1.585，所以 T(n) = O(n^1.585)。

def karatsuba(x: int, y: int) -> int:
    """Karatsuba 大整数乘法
    
    时间: O(n^log₂3) ≈ O(n^1.585)，其中 n 是位数
    """
    # 基础情况：小数直接乘
    if x < 10 or y < 10:
        return x * y
    
    # 确定分割点
    n = max(len(str(abs(x))), len(str(abs(y))))
    m = n // 2
    
    # 分割
    power = 10 ** m
    x_H, x_L = divmod(x, power)
    y_H, y_L = divmod(y, power)
    
    # 三次递归乘法（而非四次）
    z2 = karatsuba(x_H, y_H)
    z0 = karatsuba(x_L, y_L)
    z1 = karatsuba(x_H + x_L, y_H + y_L) - z2 - z0
    
    # 合并
    return z2 * (10 ** (2 * m)) + z1 * (10 ** m) + z0

实际效果： 对于 1000 位数乘法，朴素方法需要 10⁶ 次个位乘法，Karatsuba 只需约 10⁴·⁷⁵ ≈ 59000 次——加速约 17 倍。Python 的内置大整数乘法（CPython）在数字超过一定位数时就会切换到 Karatsuba 算法（源码见 Objects/longobject.c）。

2.4 Strassen 矩阵乘法简介

两个 n×n 矩阵相乘，定义式需要 O(n³) 次乘法。1969 年，Volker Strassen 发现了一个 O(n^2.807) 的分治方法——与 Karatsuba 的思路完全相同：把矩阵分成四个子块，想办法用更少的子块乘法来完成。

朴素的分块乘法需要 8 次 n/2 × n/2 的矩阵乘法（对应 T(n) = 8T(n/2) + O(n²) = O(n³)）。Strassen 通过巧妙的线性组合，把 8 次减少到 7 次：

T(n) = 7T(n/2) + O(n²) → T(n) = O(n^log₂7) = O(n^2.807)

Strassen 的 7 次乘法公式：

M₁ = (A₁₁ + A₂₂)(B₁₁ + B₂₂)
M₂ = (A₂₁ + A₂₂)B₁₁
M₃ = A₁₁(B₁₂ - B₂₂)
M₄ = A₂₂(B₂₁ - B₁₁)
M₅ = (A₁₁ + A₁₂)B₂₂
M₆ = (A₂₁ - A₁₁)(B₁₁ + B₁₂)
M₇ = (A₁₂ - A₂₂)(B₂₁ + B₂₂)

C₁₁ = M₁ + M₄ - M₅ + M₇
C₁₂ = M₃ + M₅
C₂₁ = M₂ + M₄
C₂₂ = M₁ - M₂ + M₃ + M₆

实际应用： Strassen 算法的常数因子较大（需要很多加法），所以通常在 n > 几百时才有优势。NumPy/BLAS 对小矩阵使用朴素算法，大矩阵才切换到 Strassen 或更快的算法。

目前已知最快的矩阵乘法算法的指数是约 2.371（Alman & Vassilevska Williams, 2021），但由于常数因子巨大，实际工程中没有使用。

2.5 分治在排序中的体现

归并排序和快速排序都是分治算法，但它们的分治策略截然不同：

关键洞察： 归并排序"先递归后合并"，快速排序"先分区后递归"。归并排序的工作在"归"的阶段完成，快速排序的工作在"递"的阶段完成。

def quicksort(arr: list, lo: int = 0, hi: int = None) -> None:
    """快速排序 — 原地分治
    
    与归并排序的对比:
    - 归并: 分解简单（切中间），合并复杂（merge两个有序数组）
    - 快排: 分解复杂（partition），合并简单（什么都不用做）
    """
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return
    
    # DIVIDE: partition 将数组分为 [≤pivot] [pivot] [≥pivot]
    pivot_idx = partition(arr, lo, hi)
    
    # CONQUER: 递归排序两边
    quicksort(arr, lo, pivot_idx - 1)
    quicksort(arr, pivot_idx + 1, hi)
    # COMBINE: 无需合并！因为 partition 已保证左边≤pivot≤右边


def partition(arr: list, lo: int, hi: int) -> int:
    """Lomuto 分区方案"""
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

2.6 主定理的完整应用

主定理（Master Theorem）为分治算法的递推关系提供了封闭形式解。对于递推关系：

T(n) = aT(n/b) + f(n)

其中 a ≥ 1（子问题数量），b > 1（规模缩小倍数），f(n) 是合并代价。

设 c_crit = log_b(a)，则：

应用示例：

直觉理解： c_crit = log_b(a) 衡量的是"递归树中叶子节点的总工作量"。如果 f(n) 增长慢于叶子的贡献（Case 1），总时间由叶子主导；如果两者相当（Case 2），每层贡献相同，乘以层数 log n；如果 f(n) 增长快于叶子（Case 3），总时间由根节点的合并步骤主导。

Level 3 · 规范怎么定义的

3.1 分治的历史

分治思想远比计算机科学古老。最早的已知分治算法可以追溯到 Carl Friedrich Gauss 在 1805 年手稿中描述的一种方法——后来被证明等价于快速傅里叶变换（FFT）。Gauss 在计算小行星 Pallas 的轨道时，需要计算三角级数的系数。他发现，如果将 n 个点的 DFT 分解为两个 n/2 点的 DFT，计算量可以从 O(n²) 降到 O(n log n)。

这个方法被遗忘了 150 多年，直到 Cooley 和 Tukey 在 1965 年重新发现并发表（"An Algorithm for the Machine Calculation of Complex Fourier Series", Mathematics of Computation）。Heideman, Johnson, 和 Burrus 在 1984 年的文章 "Gauss and the History of the Fast Fourier Transform" 中揭示了 Gauss 的优先权。

分治思想的其他早期实例：

• 欧几里得算法（约公元前 300 年）：gcd(a, b) = gcd(b, a mod b)。虽然通常不被归类为"分治"，但它确实将大问题归约为小问题。
• 二分搜索：最早出现在 John Mauchly 1946 年的讲座中，但正确的实现直到 1962 年才被发表。
• 归并排序：John von Neumann 在 1945 年为 EDVAC 计算机设计。
• 快速排序：Tony Hoare 在 1960 年发明，1961 年发表。

"分治"这个术语本身 最早出现在军事战略中（divide et impera，拉丁语，常归功于凯撒），被 Knuth 在 The Art of Computer Programming (1973) 中引入计算机科学。

3.2 递归的数学基础：递推关系与特征方程

递推关系（Recurrence Relation）是定义序列的方程，其中每一项由前面的项表达。求解递推关系就是找到它的封闭形式。

线性齐次递推关系 的一般形式：

a_n = c₁·a_{n-1} + c₂·a_{n-2} + ... + c_k·a_{n-k}

其特征方程为：

x^k - c₁·x^{k-1} - c₂·x^{k-2} - ... - c_k = 0

定理（特征根法）： 如果特征方程有 k 个不同的根 r₁, r₂, ..., r_k，则递推关系的通解为：

a_n = A₁·r₁ⁿ + A₂·r₂ⁿ + ... + A_k·r_kⁿ

其中 A₁, ..., A_k 由初始条件确定。

示例：求 Fibonacci 数列的封闭形式

F(n) = F(n-1) + F(n-2)，F(0)=0, F(1)=1

特征方程：x² - x - 1 = 0

解：x = (1 ± √5) / 2

设 φ = (1+√5)/2 ≈ 1.618（黄金比例），ψ = (1-√5)/2 ≈ -0.618

通解：F(n) = A·φⁿ + B·ψⁿ

代入初始条件：

• F(0) = 0: A + B = 0 → B = -A
• F(1) = 1: A·φ + B·ψ = 1 → A(φ - ψ) = 1 → A = 1/√5

因此：F(n) = (φⁿ - ψⁿ) / √5

这就是 Binet 公式（1843）。由于 |ψ| < 1，ψⁿ → 0，所以 F(n) ≈ φⁿ/√5，四舍五入到最近整数即为精确值。

这解释了为什么朴素递归 Fibonacci 的复杂度是 O(φⁿ) ≈ O(1.618ⁿ)： 因为每次调用产生两个子调用，总调用次数恰好等于 F(n+1)，由 Binet 公式知其增长率为 φⁿ。

3.3 分治与动态规划的区别

分治和动态规划都基于将问题分解为子问题，但有一个关键区别：

判断标准： 如果你画出递归树发现同一个子问题出现在多个位置（如 Fibonacci 的 fib(3) 出现多次），那就应该用动态规划；如果每个子问题只出现一次（如归并排序的每个子数组只被排序一次），那就用分治。

数学角度： 分治的递归树是一棵真正的树（无重复节点），节点数 = 子问题数。动态规划的"递归树"实际上是一个 DAG（有向无环图），如果按树展开会有指数级节点，但去重后只有多项式级别。

# 分治: 每个子问题只被解一次
def merge_sort(arr):
    # arr[0:4] 和 arr[4:8] 是不同的子问题，不会重复
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

# DP: 大量子问题重叠
def fib_memo(n, memo={}):
    # fib(3) 可能从 fib(5) 和 fib(4) 两个方向被调用
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

边界情况：有些问题既可以用分治也可以用 DP。 例如最大子数组和问题（LeetCode #53）可以用分治解（O(n log n)），也可以用 Kadane's DP 解（O(n)）。选择哪个取决于你对问题结构的理解。

3.4 Akra-Bazzi 定理

主定理虽然好用，但有严格限制：子问题规模必须相同（都是 n/b）。很多实际的分治算法不满足这个条件。例如快速排序的平均情况，partition 把数组分成 n/4 和 3n/4 两部分。

Akra-Bazzi 定理（1998）是主定理的推广，可以处理不等分的情况：

T(n) = Σᵢ aᵢ · T(bᵢ · n) + f(n)

其中 0 < bᵢ < 1，aᵢ > 0。

找到满足 Σᵢ aᵢ · bᵢᵖ = 1 的唯一实数 p，则：

T(n) = Θ(nᵖ · (1 + ∫₁ⁿ f(u)/(u^(p+1)) du))

示例：快速排序的平均情况

假设每次 partition 把数组分成 n/4 和 3n/4（不是最典型的情况，但用来说明定理）：

T(n) = T(n/4) + T(3n/4) + O(n)

Akra-Bazzi：a₁=1, b₁=1/4, a₂=1, b₂=3/4

求 p：(1/4)ᵖ + (3/4)ᵖ = 1

当 p=1 时：1/4 + 3/4 = 1 ✓

所以 T(n) = Θ(n · (1 + ∫₁ⁿ u/(u²) du)) = Θ(n · (1 + ln n)) = Θ(n log n)

这证实了即使 partition 不平衡（只要不是极端不平衡），快速排序仍然是 O(n log n)。

3.5 递归与可计算性

从理论计算机科学的角度，递归有着更深刻的意义。

原始递归函数（Primitive Recursive Functions）是通过以下基本操作构建的函数类：

1. 零函数：Z(n) = 0
2. 后继函数：S(n) = n + 1
3. 投影函数：P_i(x₁,...,x_n) = x_i
4. 复合（Composition）
5. 原始递归（Primitive Recursion）：从 f 和 g 构造 h，使得 h(0) = f，h(n+1) = g(h(n), n)

原始递归函数包含了加法、乘法、指数、阶乘等，但 不是所有可计算函数都是原始递归的。Ackermann 函数（1928）是一个可计算但非原始递归的例子——它增长得比任何原始递归函数都快。

def ackermann(m: int, n: int) -> int:
    """Ackermann 函数 — 可计算但非原始递归
    
    增长速度:
    - A(0, n) = n + 1
    - A(1, n) = n + 2  
    - A(2, n) = 2n + 3
    - A(3, n) = 2^(n+3) - 3
    - A(4, n) ≈ 2↑↑(n+3) (超指数)
    - A(4, 2) = 2^65536 - 3 (一个有约 19728 位的数)
    """
    if m == 0:
        return n + 1
    elif n == 0:
        return ackermann(m - 1, 1)
    else:
        return ackermann(m - 1, ackermann(m, n - 1))

μ-递归函数（通过添加无界搜索/最小化算子）则精确对应所有可计算函数——这就是 Church-Turing 论题的一种表述形式。

Level 4 · 边界与陷阱

4.1 Python 递归深度限制

Python 默认递归深度限制为 1000。超过这个限制会抛出 RecursionError。

import sys

# 查看当前限制
print(sys.getrecursionlimit())  # 默认 1000

# 修改限制
sys.setrecursionlimit(10000)

# 但这不是万能药！两个问题:
# 1. 操作系统的栈空间有限（通常 1-8 MB）
# 2. 即使设了 10000，如果每个栈帧很大，仍然可能 segfault

为什么 Python 要限制递归深度？

Python 使用 C 语言的调用栈来实现 Python 函数调用。C 栈的大小是固定的（Linux 默认 8MB，macOS 默认 512KB-8MB）。每个 Python 栈帧大约消耗 1-2 KB，所以 1000 层递归大约消耗 1-2 MB。如果不限制，深递归会导致 C 栈溢出，产生段错误（segmentation fault）——比抛出异常更难调试。

竞赛中的常见做法：

import sys
import threading

# 方法1：增加递归限制 + 增加线程栈大小
sys.setrecursionlimit(300000)
threading.stack_size(67108864)  # 64MB

def main():
    # 你的递归代码
    pass

thread = threading.Thread(target=main)
thread.start()
thread.join()

# 方法2：手动将递归转为迭代（更推荐）

4.2 递归转迭代的通用方法

任何递归都可以转为迭代——因为计算机本身就是用栈来实现递归的。你只需要手动模拟这个栈。

方法一：显式栈模拟

# 递归版本 DFS
def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    return visited

# 迭代版本：用显式栈
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)
    return visited

方法二：CPS 变换 + Trampoline

对于更复杂的递归（如需要后续处理的树递归），可以使用 Continuation-Passing Style (CPS) 变换：

def trampoline(fn):
    """Trampoline：避免栈溢出的递归执行器"""
    def wrapper(*args):
        result = fn(*args)
        while callable(result):
            result = result()
        return result
    return wrapper

# 使用 trampoline 实现无栈溢出的阶乘
def factorial_cps(n, cont=lambda x: x):
    if n == 0:
        return cont(1)
    # 返回一个 thunk（延迟计算），而非真正递归调用
    return lambda: factorial_cps(n - 1, lambda x: cont(n * x))

@trampoline
def factorial_safe(n, cont=lambda x: x):
    if n == 0:
        return cont(1)
    return lambda: factorial_safe(n - 1, lambda x: cont(n * x))

# factorial_safe(100000) 不会栈溢出

方法三：自底向上（当递归可以线性化时）

# 递归 Fibonacci → 迭代
# 递归方向: top-down (n → n-1 → ... → 0)
# 迭代方向: bottom-up (0 → 1 → ... → n)

def fib_bottom_up(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

4.3 面试高频题

题目 1：Pow(x, n) — LeetCode #50

def myPow(x: float, n: int) -> float:
    """实现 pow(x, n)
    
    关键陷阱:
    1. n 可能是负数
    2. n 可能是 -2^31（取反会溢出 32 位整数，但 Python 无此问题）
    3. 必须用快速幂，否则 n=2^31 时 TLE
    """
    if n < 0:
        x = 1 / x
        n = -n
    
    result = 1.0
    current_product = x
    while n > 0:
        if n & 1:
            result *= current_product
        current_product *= current_product
        n >>= 1
    return result

面试追问： 如果 x=0 且 n<0 怎么办？应该特殊处理（除零错误）。如果 x=0 且 n=0 呢？数学上 0⁰ 未定义，但 Python pow(0,0) 返回 1（计算机科学的约定）。

题目 2：多数元素 — LeetCode #169（分治解法）

def majorityElement(nums: list) -> int:
    """找出出现次数超过 n/2 的元素
    
    分治思路:
    - 如果 a 是左半数组的多数元素 或 右半数组的多数元素
    - 那么 a 可能是整个数组的多数元素
    - 验证即可
    
    时间: T(n) = 2T(n/2) + O(n) = O(n log n)
    """
    def helper(lo, hi):
        # 基础情况：单个元素
        if lo == hi:
            return nums[lo]
        
        mid = (lo + hi) // 2
        left_majority = helper(lo, mid)
        right_majority = helper(mid + 1, hi)
        
        # 如果两半的多数元素相同，直接返回
        if left_majority == right_majority:
            return left_majority
        
        # 否则，统计哪个在整个范围内出现更多
        left_count = sum(1 for i in range(lo, hi + 1) if nums[i] == left_majority)
        right_count = sum(1 for i in range(lo, hi + 1) if nums[i] == right_majority)
        
        return left_majority if left_count > right_count else right_majority
    
    return helper(0, len(nums) - 1)

面试追问： 分治解法是 O(n log n)，但存在 O(n) 的 Boyer-Moore 投票算法。分治解法的价值在于展示思维过程和分治范式，面试官可能会问"能否做到 O(n)？"

题目 3：最大子数组和 — LeetCode #53（分治 vs DP）

def maxSubArray_divide_conquer(nums: list) -> int:
    """分治解法 — O(n log n)
    
    思路: 最大子数组要么完全在左半，要么完全在右半，
         要么跨越中点。对跨越中点的情况单独计算。
    """
    def helper(lo, hi):
        if lo == hi:
            return nums[lo]
        
        mid = (lo + hi) // 2
        
        # 完全在左半的最大子数组
        left_max = helper(lo, mid)
        # 完全在右半的最大子数组
        right_max = helper(mid + 1, hi)
        
        # 跨越中点的最大子数组
        # 从 mid 向左延伸的最大和
        left_sum = float('-inf')
        curr_sum = 0
        for i in range(mid, lo - 1, -1):
            curr_sum += nums[i]
            left_sum = max(left_sum, curr_sum)
        
        # 从 mid+1 向右延伸的最大和
        right_sum = float('-inf')
        curr_sum = 0
        for i in range(mid + 1, hi + 1):
            curr_sum += nums[i]
            right_sum = max(right_sum, curr_sum)
        
        cross_max = left_sum + right_sum
        
        return max(left_max, right_max, cross_max)
    
    return helper(0, len(nums) - 1)


def maxSubArray_dp(nums: list) -> int:
    """Kadane's Algorithm — O(n) 时间, O(1) 空间
    
    DP 思路: dp[i] = 以 nums[i] 结尾的最大子数组和
    转移: dp[i] = max(nums[i], dp[i-1] + nums[i])
    """
    max_sum = curr_sum = nums[0]
    for i in range(1, len(nums)):
        curr_sum = max(nums[i], curr_sum + nums[i])
        max_sum = max(max_sum, curr_sum)
    return max_sum

分治 vs DP 的对比：

• 分治：O(n log n) 时间，O(log n) 空间，思路是"最大子数组在左/右/跨中点"
• DP（Kadane）：O(n) 时间，O(1) 空间，思路是"以每个位置结尾的最大子数组"
• 面试中如果要求分治解法，就用分治；如果要最优解，用 Kadane

题目 4：最近点对问题

import math

def closest_pair(points: list) -> float:
    """最近点对问题 — O(n log n) 分治
    
    朴素方法 O(n²)：检查所有 C(n,2) 对
    分治方法 O(n log n)：分成左右两半，分别求最近点对，
                        然后处理跨越中线的情况
    """
    def distance(p1, p2):
        return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)
    
    def closest_recursive(pts_x, pts_y):
        n = len(pts_x)
        if n <= 3:
            # 暴力
            min_dist = float('inf')
            for i in range(n):
                for j in range(i+1, n):
                    min_dist = min(min_dist, distance(pts_x[i], pts_x[j]))
            return min_dist
        
        mid = n // 2
        mid_point = pts_x[mid]
        
        # 按 x 坐标分成左右两半
        pts_y_left = [p for p in pts_y if p[0] <= mid_point[0]]
        pts_y_right = [p for p in pts_y if p[0] > mid_point[0]]
        
        # 修正：确保分割正确（处理 x 坐标相同的点）
        if len(pts_y_left) > mid:
            pts_y_left = [p for p in pts_y if p[0] < mid_point[0] or 
                         (p[0] == mid_point[0] and p[1] <= mid_point[1])]
            pts_y_right = [p for p in pts_y if p not in set(map(tuple, pts_y_left))]
        
        dl = closest_recursive(pts_x[:mid], pts_y_left)
        dr = closest_recursive(pts_x[mid:], pts_y_right)
        d = min(dl, dr)
        
        # 关键步骤：检查跨越中线的点对
        # 只需要检查 x 坐标在 [mid_x - d, mid_x + d] 范围内的点
        strip = [p for p in pts_y if abs(p[0] - mid_point[0]) < d]
        
        # 关键定理：strip 中每个点最多需要检查后面 7 个点
        # (证明见 CLRS Chapter 33)
        for i in range(len(strip)):
            j = i + 1
            while j < len(strip) and (strip[j][1] - strip[i][1]) < d:
                d = min(d, distance(strip[i], strip[j]))
                j += 1
        
        return d
    
    # 预排序
    pts_x = sorted(points, key=lambda p: p[0])
    pts_y = sorted(points, key=lambda p: p[1])
    return closest_recursive(pts_x, pts_y)

为什么 strip 中只需检查 7 个点？ 这是最近点对问题的核心引理。在宽 2d、高 d 的矩形条带中，最多有 8 个点（左右各最多 4 个，因为同侧任意两点距离 ≥ d）。排除自身后，每个点最多与 7 个点比较。这保证了 strip 步骤是 O(n)，总复杂度 T(n) = 2T(n/2) + O(n) = O(n log n)。

4.4 什么时候用分治，什么时候用 DP

这是面试中常被问到的设计决策问题。以下是判断准则：

用分治的信号：

1. 问题可以自然地分成独立的子部分（如数组的左半和右半）
2. 子问题之间不共享状态
3. 合并步骤有清晰的定义
4. 递归树是一棵真正的树（无重复子问题）

用 DP 的信号：

1. 递推关系中，同一个子问题被多次引用
2. 问题有"最优子结构"——最优解包含子问题的最优解
3. 可以定义状态转移方程
4. 子问题数量是多项式级别的

灰色地带的例子：

经验法则： 如果子问题不重叠，用分治；如果子问题重叠但你还用分治，那就是在做重复计算，应该切换到 DP（加 memoization 或自底向上）。

4.5 递归在实际工程中的应用与陷阱

陷阱 1：递归 + 全局状态 = 灾难

# 危险：递归中修改全局/共享状态
count = 0
def bad_recursive(n):
    global count
    count += 1  # 副作用！多线程下会出bug，调试困难
    if n <= 0:
        return
    bad_recursive(n - 1)

# 更好：通过参数和返回值传递状态
def good_recursive(n, count=0):
    if n <= 0:
        return count
    return good_recursive(n - 1, count + 1)

陷阱 2：递归中的浅拷贝陷阱

# 错误：回溯时 path 已被修改
def bad_backtrack(node, path, results):
    path.append(node.val)
    if not node.left and not node.right:
        results.append(path)  # 浅拷贝！后续修改会影响已保存的结果
    # ...

# 正确：存入深拷贝
def good_backtrack(node, path, results):
    path.append(node.val)
    if not node.left and not node.right:
        results.append(path[:])  # 关键：path[:] 创建副本
    if node.left:
        good_backtrack(node.left, path, results)
    if node.right:
        good_backtrack(node.right, path, results)
    path.pop()  # 回溯

陷阱 3：分治的 base case 性能

在实际实现中，当子问题规模很小时（如归并排序中只剩几个元素），递归的函数调用开销会超过实际计算开销。实际的高性能实现会在小规模时切换到简单算法：

def merge_sort_optimized(arr: list) -> list:
    """工程级归并排序：小规模时切换到插入排序"""
    CUTOFF = 16  # 实验确定的最佳切换点
    
    if len(arr) <= CUTOFF:
        # 小数组用插入排序（缓存友好，常数小）
        for i in range(1, len(arr)):
            key = arr[i]
            j = i - 1
            while j >= 0 and arr[j] > key:
                arr[j + 1] = arr[j]
                j -= 1
            arr[j + 1] = key
        return arr
    
    mid = len(arr) // 2
    left = merge_sort_optimized(arr[:mid])
    right = merge_sort_optimized(arr[mid:])
    return merge(left, right)

TimSort（Python 内置的排序算法）正是这样做的：它先用插入排序创建长度为 32-64 的有序 run，然后用归并排序合并这些 run。

4.6 分治的并行化潜力

分治算法天然适合并行化——因为子问题互相独立，可以分配给不同的处理器。

from concurrent.futures import ProcessPoolExecutor
import multiprocessing

def parallel_merge_sort(arr: list, depth: int = 0) -> list:
    """并行归并排序
    
    只在前几层使用并行（深层的子问题太小，不值得并行开销）
    """
    MAX_DEPTH = int(multiprocessing.cpu_count().bit_length())  # log₂(CPU数)
    
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    
    if depth < MAX_DEPTH:
        with ProcessPoolExecutor(max_workers=2) as executor:
            left_future = executor.submit(parallel_merge_sort, arr[:mid], depth+1)
            right_future = executor.submit(parallel_merge_sort, arr[mid:], depth+1)
            left = left_future.result()
            right = right_future.result()
    else:
        left = parallel_merge_sort(arr[:mid], depth+1)
        right = parallel_merge_sort(arr[mid:], depth+1)
    
    return merge(left, right)

Work-Span 模型： 对于并行分治算法，我们关心两个指标：

• Work W(n)：总计算量（等同于串行时间）
• Span S(n)：关键路径长度（最长依赖链）

并行加速比上限 = W(n) / S(n)（Brent's Theorem）。

对于归并排序：W(n) = O(n log n)，S(n) = O(n)（merge 是线性的，无法完全并行化）。所以并行加速比上限是 O(log n)。如果使用并行 merge（二分搜索 + 并行合并），可以将 span 降到 O(log² n)，加速比提升到 O(n / log n)。

总结

递归和分治不是两个独立的概念——分治是递归最重要的应用模式。掌握它们的关键在于：

1. 递归 = 数学归纳法在编程中的体现。三要素（基础情况、递推关系、规模缩小）缺一不可。
2. 分治 = 分解 + 递归求解 + 合并。有效的分治要求子问题独立且合并代价可控。
3. 主定理和 Akra-Bazzi 定理 给出了分治算法的时间复杂度封闭解。
4. 分治 vs DP 的判断标准：子问题是否重叠。
5. 递归转迭代：显式栈、trampoline、自底向上——三种方法覆盖所有场景。

从 Gauss 1805 年的 FFT 前身，到 Karatsuba 1960 年推翻乘法下界猜想，到 Strassen 1969 年突破矩阵乘法的 O(n³) 壁垒——分治思想在算法史上一次又一次地证明：把一个大问题变成几个小问题，往往是最深刻的解题思路。