递归与分治

在算法学习的道路上，递归（Recursion） 与 分治（Divide and Conquer） 是两座必须翻越的大山。很多初学者觉得它们抽象、难懂，甚至一看到递归就头晕。但实际上，它们是计算机科学中最优美、最核心的思想之一。

本文将从底层逻辑出发，带你彻底搞懂递归与分治的本质、区别与联系，并附带C语言实战代码。

一、 递归：把大问题变成“小一号”的自己

1. 什么是递归？

通俗地说，递归就是 “函数自己调用自己”。但绝不是无脑套娃，它必须满足两个铁律：

  • 基准情形（Base Case）：必须有一个明确的终止条件，否则就会无限递归导致栈溢出（Stack Overflow）。
  • 递归步骤（Recursive Step）：每次调用都必须让问题规模缩小，且向基准情形逼近。

💡 生活类比：你想知道自己在电影院第几排，于是问前一排的人“你在第几排？”；前一排又问再前一排……直到问到第一排的人回答“我在第1排”，然后答案逐层传回给你。这就是递归的“递”与“归”。

2. C语言经典示例：阶乘计算

1
2
3
4
5
6
7
int factorial(int n) {
    // 1. 基准情形：0! = 1
    if (n == 0) return 1;
    
    // 2. 递归步骤：n! = n * (n-1)!
    return n * factorial(n - 1);
}

3. 递归的代价

递归不是免费的午餐。每一次函数调用都会在调用栈（Call Stack） 上压入一个新的栈帧，保存局部变量和返回地址。

  • 时间开销：函数调用的压栈/弹栈操作。
  • 空间开销：递归深度为 $d$，则空间复杂度至少为 $O(d)$。

⚠️ 警告：当递归深度超过系统栈大小限制时，程序会崩溃。这是新手最常踩的坑。

二、 分治：递归的“战略升级版”

1. 什么是分治？

分治是一种算法设计策略，而递归是实现它的常用手段。分治的核心三步曲：

  1. 分解（Divide）：将原问题拆分成若干个规模更小、结构相同的子问题。
  2. 解决（Conquer）：递归地求解各子问题；若子问题足够小，直接求解。
  3. 合并（Combine）：将子问题的解合并成原问题的解。

🔑 关键区别：递归只是一种编程技巧（自己调自己），而分治是一种解决问题的方法论。分治通常用递归实现，但递归不一定是分治（比如斐波那契数列的朴素递归只是重复子问题，没有“合并”步骤，不算分治）。

2. 分治的灵魂：归并排序

归并排序是分治思想的教科书级案例，完美体现了“分解→解决→合并”的全过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 合并两个有序子数组 arr[left..mid] 和 arr[mid+1..right]
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2]; // 临时数组
    
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else              arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

// 分治主函数
void mergeSort(int arr[], int left, int right) {
    if (left >= right) return; // 基准情形：只剩一个元素
    
    int mid = left + (right - left) / 2; // 防止整数溢出
    mergeSort(arr, left, mid);           // 分解+解决左半部分
    mergeSort(arr, mid + 1, right);      // 分解+解决右半部分
    merge(arr, left, mid, right);        // 合并
}

复杂度分析：每一层合并耗时 $O(n)$，共 $\log n$ 层 → 总时间复杂度 $O(n \log n)$，且稳定。这正是分治的威力所在。

三、 递归 vs 分治：一张表理清关系

维度 递归 分治
本质 编程技巧（函数自调用） 算法设计策略
核心特征 基准情形 + 递归步骤 分解 + 解决 + 合并
子问题关系 可能重叠（如斐波那契） 通常独立、不重叠
典型应用 树遍历、阶乘、汉诺塔 归并排序、快排、大整数乘法
是否必须递归实现 是（定义即如此） 否（可用迭代/栈模拟）

四、 优化技巧

✅ 四大优化策略

优化方法 适用场景 效果
记忆化搜索 子问题重叠（如DP） 用数组/哈希表缓存结果，$O(2^n)→O(n)$
尾递归优化 递归调用是最后一步操作 编译器可复用栈帧，空间 $O(n)→O(1)$
转迭代 递归深度过大 用显式栈模拟，避免栈溢出
分治阈值切换 子问题规模很小时 切换到插入排序等简单算法，减少递归开销

💡 尾递归示例：return factorial(n-1) * n; ❌ 不是尾递归（返回后还要乘法）
return tailFactorial(n-1, acc * n); ✅ 是尾递归（返回值直接作为最终结果）