02 · 递归与分治（Recursion & Divide and Conquer）

📅 预计 100 分钟　|　⭐ 本章主题：大问题拆小问题，小问题递归套娃
📌 中英术语见文末

2.1 递归三要素

递归 = 函数调用自己，像俄罗斯套娃

递归（recursion）就是一个函数在定义里直接或间接地调用自己。想象一摞俄罗斯套娃：打开最外面一只，里面有一只更小的；再打开，又有一只更小的……直到打开最小那一只，里面什么都没有了，于是开始一只只合回去。

写递归要满足三个要素：

基线条件（base case）：规模小到不能再小，直接返回结果，不再调用自己——这就是"最小的套娃"。没有它，递归永远停不下来。
递归条件（recursive case）：把问题拆成更小的同类问题，然后调用自己。
规模必须减小：每次递归调用都在朝基线条件逼近，否则会无限递归。

最经典的例子是阶乘 n! = n × (n-1)!：

def factorial(n):
    if n <= 1:            # 基线条件：0! 和 1! 都是 1
        return 1
    return n * factorial(n - 1)   # 递归条件：缩小规模，调用自己

print(factorial(5))
# 输出: 120
print(factorial(0))
# 输出: 1

运行过程可以展开成一张"账本"：

factorial(5)
  = 5 * factorial(4)
    = 5 * 4 * factorial(3)
      = 5 * 4 * 3 * factorial(2)
        = 5 * 4 * 3 * 2 * factorial(1)
          = 5 * 4 * 3 * 2 * 1
          = 120

⚠️ 常见错误

忘记基线条件：def f(n): return n + f(n-1) 没有出口，运行报 RecursionError。
基线条件写错，永远达不到：if n == 1 却传了 n=0，会一路递归到负无穷。
规模没有减小：递归里传 factorial(n) 而不是 factorial(n-1)，死循环。

2.2 调用栈与栈溢出

递归的秘密武器：调用栈

为什么函数调用完还能回到调用处继续执行？因为系统维护着一块调用栈（call stack）——每调用一个函数，就把它的"现场"（局部变量、返回地址）压进栈顶；函数返回时再弹出栈顶，恢复现场。递归就是一次次压栈的过程。

def greeting(n):
    if n <= 0:
        return
    print(f"压栈: greeting({n})")
    greeting(n - 1)                 # 调自己前，当前现场被压栈
    print(f"出栈: 回到 greeting({n})")
    return

greeting(3)
# 输出:
# 压栈: greeting(3)
# 压栈: greeting(2)
# 压栈: greeting(1)
# 出栈: 回到 greeting(1)
# 出栈: 回到 greeting(2)
# 出栈: 回到 greeting(3)

注意"压栈"是深度优先的：先一路压到底，再一层层弹出。这也解释了递归深度 n 时的空间复杂度是 O(n)——栈里最多同时存在 n 个函数的现场。

栈溢出（stack overflow）：栈空间是有限的。Python 默认把递归深度限制在约 1000 层，超过就抛 RecursionError。可以查和改这个限制（不推荐为了绕过而调大）：

import sys
print(sys.getrecursionlimit())   # 输出: 1000（默认值，不同版本可能不同）

# 试试超深递归会怎样（会抛异常，运行前先想清楚）
# def boom(n): return 1 + boom(n - 1)
# boom(2000)   # RecursionError: maximum recursion depth exceeded

💡 记忆口诀：递归 = 一路压栈到底 + 一路弹栈回来；栈满则溢。深递归小心 RecursionError。

⚠️ 常见错误

以为递归不占额外空间：每次调用都压栈，深度 n 的递归空间复杂度是 O(n)。
盲目调大递归限制：sys.setrecursionlimit(10**6) 只改了上限，栈内存还是有限，深度过大照样崩（甚至崩溃更难看）。深递归应改写为迭代。
把递归展开顺序想成"从上到下"：实际是先压到底，再从底往回算，很多题目的答案是在"出栈"阶段得到的。

2.3 斐波那契：朴素递归与优化 ⭐

朴素递归很美，但会指数爆炸

斐波那契数列：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。按定义直接写递归非常自然：

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))
# 输出: 55

但它慢得惊人。看 fib(5) 的调用展开，会发现 fib(3) 被算了 2 次、fib(2) 被算了 3 次、fib(1) 被算了 5 次——同一个子问题反复计算。可以证明朴素递归的时间复杂度是 O(2ⁿ)：n=40 就已经是万亿次运算，跑不动。

一个直观的计数验证：

calls = 0
def fib_count(n):
    global calls
    calls += 1
    if n <= 1:
        return n
    return fib_count(n - 1) + fib_count(n - 2)

fib_count(10)
print(f"fib(10) 一共调用了 {calls} 次函数")
# 输出: fib(10) 一共调用了 177 次函数

优化一：记忆化（备忘录）

既然子问题被反复算，那算过一次就存起来，下次直接查表。用 lru_cache 装饰器最省事：

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

print(fib_memo(100))
# 输出: 354224848179261915075

每个 n 只算一次，复杂度降到 O(n)，空间 O(n)。注意 lru_cache 要求参数可哈希（整数完全没问题）。

优化二：迭代（自底向上）

更省空间的写法：从 F(0)、F(1) 一步步往上滚，只用两个变量，空间 O(1)：

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_iter(100))
# 输出: 354224848179261915075

💡 记忆口诀：递归的思路"从上往下拆"，迭代的写法"从下往上滚"。拆要记忆化，滚只用两个变量。

⚠️ 常见错误

直接写朴素递归交差：写法漂亮但 O(2ⁿ)，n 稍大就卡死，必须记忆化或迭代。
lru_cache 忘了 import：from functools import lru_cache 必不可少。
迭代版初始值搞反：a, b = 0, 1 再滚 n 次返回 a，别把 a, b 顺序写反成 1, 0。

2.4 分治三步

分治 = 分而治之：拆、算、合

分治算法（divide and conquer）是递归最经典的应用，核心套路只有三步：

分解（divide）：把原问题拆成若干个规模更小、结构相同的子问题；
解决（conquer）：子问题小到可直接求解，或递归地继续分解直到可解；
合并（merge）：把子问题的解组合成原问题的解。

判断一个问题能不能用分治，看两点：子问题与原问题同构（只是规模更小），并且合并结果能还原原问题。本章的二分查找、归并排序、快速排序全是这个套路。

# 分治求数组和：把数组劈两半，分别求和再加起来
def sum_list(arr):
    if len(arr) == 0:          # 基线：空数组和为 0
        return 0
    if len(arr) == 1:          # 基线：单元素
        return arr[0]
    mid = len(arr) // 2        # 分解
    left = sum_list(arr[:mid])      # 递归解决左半
    right = sum_list(arr[mid:])     # 递归解决右半
    return left + right             # 合并

print(sum_list([1, 2, 3, 4, 5]))
# 输出: 15

⚠️ 常见错误

子问题忘记"同构"：如果拆出来的子问题跟原问题不是同一类，递归就没法写。
合并步骤缺失或写错：分治一定要有合并，二分查找是特例——它只需要返回其中一半，不需要真正合并。
基线条件不完整：空数组、单元素这类边界没处理，递归直接越界崩溃。

2.5 二分查找 ⭐

猜数字游戏：每次排除一半

二分查找（binary search）的前提是数组已有序。每次取中间元素跟目标比较：相等就命中；比目标小，说明目标只可能在右半；比目标大，只在左半。每比较一次，搜索区间减半。

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid            # 找到，返回下标
        elif arr[mid] < target:
            left = mid + 1        # 目标在右半
        else:
            right = mid - 1       # 目标在左半
    return -1                     # 没找到

nums = [1, 3, 5, 7, 9, 11]
print(binary_search(nums, 7))   # 输出: 3
print(binary_search(nums, 4))   # 输出: -1

复杂度推导：n 个元素，第一次剩 n/2，第二次 n/4……第 k 次剩 n/2ᵏ。当 n/2ᵏ = 1 时 k = log₂n，所以时间复杂度 O(log n)，空间 O(1)。对比顺序查找的 O(n)，n=100 万时一个是 20 步，一个是 100 万步。

三个易错细节：

mid = (left + right) // 2 要向下取整，避免死循环；
循环条件是 left <= right，漏掉 = 会漏掉 left == right 的最后一个元素；
left = mid + 1 / right = mid - 1 必须跳过 mid，否则会无限循环。

💡 记忆口诀：左闭右闭查中间，小则左移大则右移；区间缩到空，目标不存在。

⚠️ 常见错误

没排序就用二分：乱序数组里二分结果完全错误——二分的前提是有序。
死循环：改 left = mid 或 right = mid 且不跳过 mid，区间永远缩不小。
返回位置记错：有时题目要返回"第一个 ≥ 目标的位置"而非精确命中，注意区分。

2.6 归并排序 ⭐

分治排序：拆到单元素，再两两有序合并

归并排序（merge sort）完美演示分治三步：

分解：把数组从中间劈成两半，递归劈到每段只剩 1 个元素（1 个元素天然有序）；
解决：递归对左右两半各自排序；
合并：把两个已有序的子数组合并成一个有序数组——同时比较两个数组头，小的先出。

def merge_sort(arr):
    if len(arr) <= 1:                  # 基线：空或单元素已有序
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])       # 递归排序左半
    right = merge_sort(arr[mid:])      # 递归排序右半
    return merge(left, right)          # 合并两个有序数组

def merge(a, b):
    i = j = 0
    res = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            res.append(a[i]); i += 1
        else:
            res.append(b[j]); j += 1
    res.extend(a[i:])                  # 收尾
    res.extend(b[j:])
    return res

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# 输出: [3, 9, 10, 27, 38, 43, 82]

复杂度：T(n) = 2·T(n/2) + O(n)。每一层合并要扫一遍全部 n 个元素，一共 log₂n 层，所以总时间复杂度 O(n log n)，且最坏也是 O(n log n)——这是它的最大优点。代价是每次合并都新建数组，空间复杂度 O(n)。归并是稳定排序（见第 03 章）。

💡 记忆口诀：分而合之，层层合并扫一遍，共 log n 层 → O(n log n)。

⚠️ 常见错误

合并时丢掉尾部：while 循环结束后，剩下的一截要用 extend 补上，漏了就丢元素。
以为归并不稳定：合并时 a[i] <= b[j] 取左边，保证相等时原顺序不变，是稳定的。
忘记基线：len(arr) <= 1 不写，单元素数组无限递归。

2.7 快速排序 ⭐

分治排序：选个基准，小的靠左、大的靠右

快速排序（quick sort）的思想：选一个基准（pivot），把数组分成"比基准小"和"比基准大"两拨，然后递归对两拨分别排序——基准自己已经处在最终位置，所以不需要合并。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]        # 选中间元素当基准（简单实现）
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quick_sort(less) + equal + quick_sort(greater)

print(quick_sort([3, 6, 8, 10, 1, 2, 1]))
# 输出: [1, 1, 2, 3, 6, 8, 10]

上面的写法每次建三个新列表，好懂但耗空间；实际库实现用原地 partition（一趟把小于基准的换到左边、大于的换到右边），空间复杂度做到 O(log n)。原地划分是面试手写快排的标准考法，思路是双指针：从左找大于基准的、从右找小于基准的，交换。

复杂度：平均情况 O(n log n)；但最坏情况是 O(n²)——当每次选的基准都是当前区间的最小或最大值（比如已有序数组 + 选第一个元素当基准），分解根本不均匀，退化成每次只减少一个元素。这也是"平均好、最坏差"的代表算法。

# 原地 partition 的快排（面试标准写法）
def quick_sort_inplace(arr, lo, hi):
    if lo >= hi:
        return
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] < pivot:           # 小的换到左边
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]  # 基准归位
    quick_sort_inplace(arr, lo, i - 1)
    quick_sort_inplace(arr, i + 1, hi)

nums = [3, 6, 8, 10, 1, 2, 1]
quick_sort_inplace(nums, 0, len(nums) - 1)
print(nums)
# 输出: [1, 1, 2, 3, 6, 8, 10]

⚠️ 常见错误

最坏情况背不出来：快排最坏是 O(n²)（已有序数据 + 选端点做基准），不是 O(n log n)。
原地 partition 死循环：两个指针相遇条件、边界 lo/hi 写错，递归停不下来。
忽略相等元素：partition 对等于基准的元素处理不当，会导致左右严重不均，退化更严重。

2.8 主定理直观理解

不用背公式，先看懂它说什么

分治算法常写成递归式 T(n) = a·T(n/b) + f(n)，含义：规模 n 的问题，拆成 a 个规模 n/b 的子问题，拆分与合并的成本是 f(n)。主定理（Master Theorem）给出了这类递归式的复杂度结论。教材通常给三种情况，这里用直觉记住框架：

关键变量：n^(log_b a)——这是"叶子总数"带来的成本。如果拆出 a 个 n/b 的子问题，总叶子规模就是 a^(log_b n) = n^(log_b a)。
把 n^(log_b a) 和 f(n)（每层拆分合并成本）比大小：
1. 叶子成本主导（f(n) 相对更小）→ 复杂度为 O(n^(log_b a))；
2. 两者相当 → 多乘一个 log：O(n^(log_b a) · log n)；
3. 拆分成本主导（f(n) 相对更大）→ 复杂度由 O(f(n)) 主导（还需满足正则条件，细节略）。

拿归并排序 T(n) = 2·T(n/2) + O(n) 验证：a=2, b=2，log_b a = log₂2 = 1，所以 n^(log_b a) = n。f(n)=n 与 n 相当，属于情况 2 → O(n log n)，与实际完全一致。

💡 记忆口诀：主定理比"叶子成本 n^(log_b a)"和"每层成本 f(n)"谁大：叶子大看叶子，合并大看合并，势均力敌乘 log。

⚠️ 常见错误

套公式前不确认形式：主定理只适用 T(n) = a·T(n/b) + f(n) 这种"均匀拆分"；拆分不均匀（如快排最坏 T(n) = T(n-1) + n）不适用，直接算即可。
背错情况：情况 2 要多乘一个 log n，这是 n log n 的来源，最常被忽略。
忽略 f(n) 的相对大小：是"比 n^(log_b a) 大/小/相当"，不是看 f(n) 本身大不大。

🧠 记忆口诀

递归三要素：基线出口、递归调用、规模递减——三者缺一就栈溢出。
调用栈：压栈到底再弹栈，递归深度即栈空间 O(n)。
斐波那契：朴素 O(2ⁿ) 会爆炸，记忆化或迭代降到 O(n)。
分治三步：分解、解决、合并——拆成同构子问题，递归处理，结果合起来。
二分 O(log n)：区间每次减半，前提是已排序。
归并稳定 O(n log n)：拆到单元素，两两有序合并。
快排平均 O(n log n)、最坏 O(n²)：基准选不好就退化。
主定理：叶子成本 vs 每层成本，谁大听谁的，相当就乘 log。

📌 中英术语表（本讲）

中文	English	说明
递归	recursion	函数调用自己
基线条件	base case	递归出口，不再调用自己
递归条件	recursive case	拆成更小同构问题的部分
调用栈	call stack	函数调用的压栈/弹栈现场
栈溢出	stack overflow	递归深度超限崩溃
记忆化	memoization	缓存已算子问题的结果
分治	divide and conquer	分解→解决→合并
二分查找	binary search	有序数组中每次砍半查找
归并排序	merge sort	拆到单元素再两两合并
快速排序	quick sort	选基准划分，递归排序两侧
基准 / 枢轴	pivot	快速排序选的分界元素
原地划分	in-place partition	一趟把元素按基准分两侧
递归式	recurrence	用自身表示复杂度的等式
主定理	Master Theorem	求解递归式的三条结论
稳定排序	stable sort	相等元素保持原相对顺序

⭐ 本章考点清单

递归三要素：基线、递归、规模递减
调用栈机制与递归的空间复杂度 O(n)；RecursionError 成因
斐波那契朴素 O(2ⁿ)、记忆化 O(n)、迭代 O(n) 空间 O(1)
分治三步：分解 / 解决 / 合并
二分查找代码与 O(log n) 推导；left <= right、mid ± 1 细节
归并排序代码、O(n log n)、稳定、空间 O(n)
快速排序代码、平均 O(n log n)、最坏 O(n²)（已有序 + 选端点基准）
主定理：n^(log_b a) 与 f(n) 三情形，归并 T(n)=2T(n/2)+n 属情形 2
递归 vs 迭代改写（栈溢出时的应对）