递归与分治

🪆 俄罗斯套娃——自己里面还装着自己

你打开一个俄罗斯套娃。里面露出一个小一点儿的娃娃。你再打开它——里面又有一个更小的。再打开……

最小的那个娃娃已经不能打开了。但它也是套娃——只是它是最小、不能拆分的那一个。

这就是递归（Recursion）：一个东西的定义里包含了它自己。

在编程中，递归就是”函数调用自身”。但这不应该是无限循环——必须有一个终止条件（就像最小的俄罗斯套娃，不能再打开）。

而分治（Divide and Conquer） 则是一类利用递归的算法设计思想：把一个大问题分解成若干个小问题，分别解决小问题，再合并结果。

🎯 类比：军训喊口令

连长说”各排报数！”。

一排长喊：“二排长，你们排多少人？“（分解） 二排长喊：“三排长，你们排多少人？” ……（继续分解） 最后一个排长喊：“我们排 30 人！“（最小子问题——基线条件） 倒数第二个排长算了算：“我们排 25 人，加上最后一排 30 人，一共 55 人”（合并） ……（继续合并） 一排长：“全连 200 人！”

这就是分治：把”算全连人数”分解成”算每个排的人数”，排再分解成班，最小的班直接知道人数。然后逐层合并结果。

---

🔄 递归——两个要素

任何一个正确的递归函数，必须有两个要素：

要素 1：基线条件（Base Case）

递归的”出口”——问题足够小，可以直接解决，不再需要递归。

要素 2：递归步骤（Recursive Step）

把问题转化成”更小的同类问题”，然后调用自身。

# 阶乘 n! = n × (n-1) × (n-2) × ... × 1
def factorial(n):
    # 基线条件
    if n <= 1:
        return 1
    
    # 递归步骤：n! = n × (n-1)!
    return n * factorial(n - 1)

# 执行过程：
# factorial(4) = 4 * factorial(3)
#             = 4 * (3 * factorial(2))
#             = 4 * (3 * (2 * factorial(1)))
#             = 4 * (3 * (2 * 1))
#             = 24

调用栈的变化：
factorial(4)  → 调用 factorial(3) → 调用 factorial(2) → 调用 factorial(1)
                                                          ↓ 返回 1
                                              ← 返回 2 * 1 = 2
                             ← 返回 3 * 2 = 6
             ← 返回 4 * 6 = 24

💡 递归的本质是”栈”——每次函数调用把当前状态压入调用栈，基线条件触发后开始逐层”弹出”。这也意味着递归深度过大时会导致”栈溢出”。

---

🧩 分治——三步法

分治（Divide and Conquer）是递归最重要的应用。它把问题按三个步骤解决：

1. 分解（Divide）：把原问题分解成若干个子问题
                  子问题是原问题的"缩小版"
2. 解决（Conquer）：递归地解决子问题
                   当子问题足够小时，直接解决
3. 合并（Combine）：把子问题的解合并成原问题的解

例子：用分治找最大值

def find_max(arr):
    # 基线：只有一个元素，最大值就是它自己
    if len(arr) == 1:
        return arr[0]
    
    # 分解：分成两半
    mid = len(arr) // 2
    left_max = find_max(arr[:mid])
    right_max = find_max(arr[mid:])
    
    # 合并：取两个最大值中更大的
    return max(left_max, right_max)

# 执行过程：
# find_max([3, 8, 2, 5])
# ├─ find_max([3, 8])
# │  ├─ find_max([3]) → 3
# │  └─ find_max([8]) → 8
# │  └─ max(3, 8) → 8
# ├─ find_max([2, 5])
# │  ├─ find_max([2]) → 2
# │  └─ find_max([5]) → 5
# │  └─ max(2, 5) → 5
# └─ max(8, 5) → 8

---

🏢 递归 vs 迭代

维度	递归	迭代
代码简洁性	✅ 简洁，和数学定义一致	❌ 通常需要更多代码
可读性	✅ 分治思想自然表达	❌ 需要追踪循环变量
性能	❌ 函数调用有开销	✅ 更高效
栈溢出风险	❌ 深度太大会栈溢出	✅ 没有这个风险
调试难度	❌ 调用链长时难追踪	✅ 更容易单步调试

什么时候用递归？

# ✅ 适合递归
# 树和图遍历
def traverse_tree(node):
    if not node:
        return
    print(node.val)
    traverse_tree(node.left)
    traverse_tree(node.right)

# 分治算法（归并排序、快排）
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    # ...

# ❌ 不适合递归
# 简单的循环——迭代更高效
def sum_arr(arr):
    total = 0
    for x in arr:
        total += x
    return total
# 用递归写就是"为了递归而递归"——没必要

---

🎯 分治的经典应用

你已经学过的一些算法，其实都是分治思想的应用：

算法	分治过程
归并排序	分解：分成两半。解决：递归排序。合并：合并两个有序数组
快速排序	分解：选 pivot 分区。解决：递归排序两边。合并：不需要！
二分搜索	分解：取中间值。解决：在左边或右边继续找。合并：不需要
二叉树遍历	分解：左子树和右子树。解决：递归遍历。合并：访问根节点（的位置不同）

主定理（Master Theorem）——分析分治算法的时间复杂度

分治算法的时间复杂度通常满足一个公式：

$$ T(n) = aT(n/b) + O(n^d) $$

其中：

• a = 递归中分解成几个子问题
• b = 每个子问题的规模是原问题的 1/b
• O(n^d) = 分解和合并的代价

主定理直接给出结果：

a < b^d  → T(n) = O(n^d)         （例：二分搜索 a=1,b=2,d=0 → O(log n)）
a = b^d  → T(n) = O(n^d log n)   （例：归并排序 a=2,b=2,d=1 → O(n log n)）
a > b^d  → T(n) = O(n^log_b(a))  （例：暴力递归 a=3,b=2,d=0 → O(n^1.585)）

---

📝 小结

概念	一句话
递归	函数调用自身——自己里面又包含自己
基线条件	递归的出口——问题足够小直接解决
分治	分解→解决→合并——把大问题拆成小问题
调用栈	递归的底层机制——每次调用压栈，返回时出栈
主定理	分析分治算法时间复杂度的公式
适用场景	树/图遍历、分治排序、搜索问题

🎯 小练习：用递归实现”反转字符串”函数。提示：把字符串分解成”第一个字符”和”剩余部分”。

为什么先学这个？ 分治是算法设计的第一种核心思想。接下来学习它的”升级版”——动态规划，通过”记住子问题的答案”来避免重复计算。