【算法设计与分析】（二）什么是递归，以及分治法的基本思想

---

前言

• 在上一篇博客中，我们深入探讨了算法的本质与核心概念，明确了算法作为解决问题的系统性步骤的重要意义。
• 接下来，我们将开启新的探索之旅，深入理解递归的本质，并解析分治法的核心思想 —— 这两种计算机科学中极具智慧的问题解决策略，不仅在算法设计中占据关键地位，更蕴含着化繁为简的底层逻辑

我的个人主页，欢迎来阅读我的其他文章
https://blog.csdn.net/2402_83322742?spm=1011.2415.3001.5343
我的算法与设计博客专栏
https://blog.csdn.net/2402_83322742/category_12903664.html?spm=1001.2014.3001.5482

---

一、什么是递归

1. 递归的本质

递归的核心思想很简单：一个问题可以通过解决更小的同类问题来解决。就像俄罗斯套娃，打开一个大娃娃，里面是更小的娃娃，直到找到最小的那个（基线条件）。

比如，计算阶乘 n!（n的阶乘）：

• 数学定义：n! = n × (n-1) × (n-2) × ... × 1
• 递归定义：n! = n × (n-1)!，其中 0! = 1（基线条件）。
  这里，计算 5! 时，会先算 4!，再算 3!……直到 0!，然后层层返回结果。

2. 递归的两个关键要素

• 基线条件：递归停止的“终点”，就像最小的套娃，必须明确且可直接解决。
• 递归调用：将问题分解为更小的同类问题，逐步靠近基线条件。

3. 用C语言实现阶乘递归

#include <stdio.h>// 递归计算n的阶乘
int factorial(int n) {// 基线条件：0! = 1if (n == 0) {return 1;}// 递归调用：n! = n × (n-1)!return n * factorial(n-1);
}int main() {int n = 5;int result = factorial(n);printf("%d! = %d\n", n, result);  // 输出：5! = 120return 0;
}

代码解析：

• 当 n=0 时，直接返回1（基线条件）。
• 否则，返回 n 乘以 (n-1) 的阶乘（递归调用），直到 n 减到0。

4. 递归的注意事项

• 必须有基线条件，否则会陷入无限递归（类似死循环），导致程序崩溃。
• 递归过程会消耗内存（系统用“栈”存储每一层调用），如果问题规模太大，可能导致“栈溢出”。

二、分治法（分割法）的基本思想

1. 分治法的核心

分治法的思想可以概括为三个步骤：

1. 分解（Divide）：把大问题拆分成多个规模更小、结构相同的子问题。
2. 解决（Conquer）：递归解决每个子问题（如果子问题足够小，直接解决）。
3. 合并（Combine）：把各个子问题的解合并成原问题的解。

2. 分治法与递归的关系

分治法通常用递归实现：分解后的子问题和原问题结构相同，适合用递归调用处理。

3. 用C语言实现二分查找（分治法经典案例）

二分查找的目标是在有序数组中快速找到目标值，其分治思想如下：

• 分解：取数组中间元素，比较后只处理左半部分或右半部分。
• 解决：递归在左半或右半部分查找。
• 合并：找到目标值则返回位置，否则返回-1。

#include <stdio.h>// 递归实现二分查找
int binarySearch(int arr[], int left, int right, int target) {// 基线条件：查找范围为空，没找到if (left > right) {return -1;}// 分解：计算中间位置int mid = left + (right - left) / 2;// 解决：根据中间元素与目标值的关系，递归处理左半或右半部分if (arr[mid] == target) {return mid;  // 找到目标值，返回位置} else if (arr[mid] < target) {// 目标值在右半部分，递归查找右半部分return binarySearch(arr, mid + 1, right, target);} else {// 目标值在左半部分，递归查找左半部分return binarySearch(arr, left, mid - 1, target);}
}int main() {int arr[] = {1, 3, 5, 7, 9, 11, 13};int n = sizeof(arr) / sizeof(arr[0]);int target = 7;int position = binarySearch(arr, 0, n - 1, target);if (position == -1) {printf("未找到目标值 %d\n", target);} else {printf("目标值 %d 在数组中的位置是 %d\n", target, position);}return 0;
}

代码解析：

• 每次查找将数组分成两半，只处理可能包含目标值的一半，时间复杂度为 O(log n)，比遍历（O(n)）快很多。
• 基线条件是 left > right，即查找范围为空时返回-1。

4. 分治法的典型应用代码实现与讲解

4.1 归并排序

思想：将数组分成两半，分别排序后合并。
步骤：

1. 分解：将数组从中间分成两部分。
2. 解决：递归排序左右两部分。
3. 合并：将已排序的两部分合并成一个有序数组。

#include <stdio.h>// 合并两个已排序的子数组
void merge(int arr[], int left, int mid, int right) {int i, j, k;int n1 = mid - left + 1;int n2 = right - mid;// 创建临时数组int L[n1], R[n2];// 复制数据到临时数组 L[] 和 R[]for (i = 0; i < n1; i++)L[i] = arr[left + i];for (j = 0; j < n2; j++)R[j] = arr[mid + 1 + j];// 合并临时数组回原数组i = 0;      // 初始化左子数组的索引j = 0;      // 初始化右子数组的索引k = left;   // 初始归并子数组的索引while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// 复制 L[] 的剩余元素while (i < n1) {arr[k] = L[i];i++;k++;}// 复制 R[] 的剩余元素while (j < n2) {arr[k] = R[j];j++;k++;}
}// 归并排序主函数
void mergeSort(int arr[], int left, int right) {if (left < right) {// 找到中间点int mid = left + (right - left) / 2;// 递归排序左右两部分mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);// 合并已排序的两部分merge(arr, left, mid, right);}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};int arr_size = sizeof(arr) / sizeof(arr[0]);printf("原数组: \n");printArray(arr, arr_size);mergeSort(arr, 0, arr_size - 1);printf("排序后的数组: \n");printArray(arr, arr_size);return 0;
}

代码解析：

• mergeSort 递归分解数组，直到每个子数组只剩1个元素（自然有序）。
• merge 函数将两个有序子数组合并，通过比较元素逐个放入原数组。
• 时间复杂度始终为 O(n log n)，空间复杂度为 O(n)（需要临时数组）。

4.2 快速排序

思想：选择基准值（pivot），将数组分为两部分，左边比基准小，右边比基准大，再递归排序。
步骤：

1. 分解：选择基准值，将数组分为两部分。
2. 解决：递归排序左右两部分。
3. 合并：无需合并，分解时已保证左右有序。

#include <stdio.h>// 交换两个元素
void swap(int* a, int* b) {int t = *a;*a = *b;*b = t;
}// 分区函数，选择最后一个元素作为基准
int partition(int arr[], int low, int high) {int pivot = arr[high];  // 基准值int i = (low - 1);      // 小于基准的元素的索引for (int j = low; j <= high - 1; j++) {// 如果当前元素小于等于基准if (arr[j] <= pivot) {i++;    // 增加小于基准的元素的索引swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]);return (i + 1);
}// 快速排序主函数
void quickSort(int arr[], int low, int high) {if (low < high) {// 分区索引，pivot 已就位int pi = partition(arr, low, high);// 递归排序左右两部分quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");
}int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码解析：

• partition 函数选择最后一个元素为基准，将小于等于基准的元素移到左边，返回基准的最终位置。
• quickSort 递归处理基准左右两部分。
• 平均时间复杂度为 O(n log n)，但最坏情况（如数组已有序）为 O(n²)。

4.3 汉诺塔问题

问题：将N个盘子从柱子A移动到柱子C，每次只能移动一个盘子，且大盘不能放在小盘上。
思想：递归地将N-1个盘子从A移到B，再将第N个盘子从A移到C，最后将N-1个盘子从B移到C。

#include <stdio.h>// 汉诺塔递归函数
void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {if (n == 1) {printf("移动盘子 1 从柱子 %c 到柱子 %c\n", from_rod, to_rod);return;}// 将 n-1 个盘子从 A 移到 B，借助 CtowerOfHanoi(n - 1, from_rod, aux_rod, to_rod);// 将第 n 个盘子从 A 移到 Cprintf("移动盘子 %d 从柱子 %c 到柱子 %c\n", n, from_rod, to_rod);// 将 n-1 个盘子从 B 移到 C，借助 AtowerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}int main() {int n = 3;  // 盘子数量towerOfHanoi(n, 'A', 'C', 'B');  // 从 A 柱移到 C 柱，借助 B 柱return 0;
}

代码解析：

• 当 n=1 时，直接移动盘子（基线条件）。
• 否则，递归处理三个步骤：移动N-1个盘子到辅助柱，移动第N个盘子，再移动N-1个盘子到目标柱。
• 需要移动的总次数为 2ⁿ - 1，时间复杂度为 O(2ⁿ)（指数级）。

---

以上就是对本次博客所有内容，后续我们将深入探讨算法与设计更多知识。

我的个人主页，欢迎来阅读我的其他文章
https://blog.csdn.net/2402_83322742?spm=1011.2415.3001.5343
我的算法与设计博客专栏
https://blog.csdn.net/2402_83322742/category_12903664.html?spm=1001.2014.3001.5482

非常感谢您的阅读，喜欢的话记得三连哦