递归是C++中一种重要的编程思想，指函数在其内部调用自身的编程方式，而分治法是把复杂问题拆分成多个规模更小的相同子问题，直到子问题可以直接求解，再合并结果得到原问题答案。递归和分治法的结合能有效简化很多复杂问题的实现逻辑。
C++函数递归的核心要素
要实现正确的递归函数，必须满足两个核心条件，否则会导致程序运行异常。
- 终止条件：必须存在明确的递归终止场景，当满足该条件时函数不再调用自身，直接返回结果，避免无限递归导致栈溢出。
- 递归调用：在函数内部调用自身，且每次调用的参数规模要比上一次更小，逐步向终止条件靠近。
我们可以用计算阶乘的场景来理解基础递归，示例代码如下：
#include <iostream>
using namespace std;
// 计算n的阶乘，n为正整数
int factorial(int n) {
// 终止条件：0的阶乘为1，1的阶乘也为1
if (n == 0 || n == 1) {
return 1;
}
// 递归调用：n! = n * (n-1)!
return n * factorial(n - 1);
}
int main() {
int num = 5;
cout << num << "的阶乘是：" << factorial(num) << endl;
return 0;
}分治法的核心逻辑
分治法的执行流程可以分为三个步骤：
- 分：将原问题拆分成多个规模更小、结构相同的子问题。
- 治：递归求解每个子问题，如果子问题规模足够小可直接求解，就直接返回结果。
- 合：将各个子问题的解合并，得到原问题的解。
分治法天然适合用递归实现，因为拆分后的子问题和原问题结构完全一致，刚好符合递归调用的特征。
分治法中递归的应用示例：归并排序
归并排序是典型的用分治法+递归实现的排序算法，它的核心逻辑就是不断拆分数组，排序子数组后再合并。
完整实现代码如下：
#include <iostream>
#include <vector>
using namespace std;
// 合并两个有序数组
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int> temp;
int i = left, j = mid + 1;
// 比较两个有序数组的元素，按顺序放入临时数组
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp.push_back(arr[i]);
i++;
} else {
temp.push_back(arr[j]);
j++;
}
}
// 将剩余元素放入临时数组
while (i <= mid) {
temp.push_back(arr[i]);
i++;
}
while (j <= right) {
temp.push_back(arr[j]);
j++;
}
// 将排序好的结果拷贝回原数组
for (int k = 0; k < temp.size(); k++) {
arr[left + k] = temp[k];
}
}
// 归并排序递归函数，分治法的递归实现
void mergeSort(vector<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);
}
int main() {
vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
int n = arr.size();
mergeSort(arr, 0, n - 1);
cout << "排序后的数组：";
for (int num : arr) {
cout << num << " ";
}
cout << endl;
return 0;
}递归使用的注意事项
在分治法中使用递归时，需要注意以下几点避免出错：
- 一定要明确终止条件，且每次递归的参数必须向终止条件靠近，否则会出现无限递归，导致程序栈溢出崩溃。
- 递归调用的深度不要过深，因为每次函数调用都会在栈上分配空间，深度过深同样会引发栈溢出问题。
- 拆分问题时，要保证子问题和原问题结构完全一致，且子问题的解可以正确合并为原问题的解，否则分治逻辑会出错。
注意：除了归并排序，快速排序、二分查找等算法也都是分治法结合递归的典型应用，理解了这个模式后可以快速掌握这类算法的实现逻辑。
通过分治法中的递归应用可以看到，递归可以把复杂的问题拆分逻辑简化，减少重复代码，但也需要合理设计终止条件和拆分逻辑，才能写出正确高效的代码。