【数据结构与算法】第46篇：算法思想（一）：递归与分治

一、递归的本质1.1 什么是递归递归就是函数调用自身。一个递归函数通常包含两部分终止条件什么时候停止递归递推公式如何将大问题转化为小问题c// 阶乘的递归实现 int factorial(int n) { if (n 1) return 1; // 终止条件 return n * factorial(n - 1); // 递推公式 }1.2 递归的底层原理系统栈每次函数调用系统都会在栈上分配空间存储函数的参数局部变量返回地址当函数调用结束时栈帧被弹出程序回到调用点继续执行。以 factorial(3) 为例text调用 factorial(3): 栈: [fact(3)] 调用 factorial(2): 栈: [fact(3), fact(2)] 调用 factorial(1): 栈: [fact(3), fact(2), fact(1)] 返回 1 栈: [fact(3), fact(2)] 计算 2 * 1 2返回 栈: [fact(3)] 计算 3 * 2 6返回 栈: []递归深度栈中最多同时存在的栈帧数量。深度过大如递归10000次会导致栈溢出。1.3 递归 vs 迭代对比项递归迭代代码可读性简洁直观相对复杂空间复杂度O(递归深度)O(1)性能函数调用开销大循环开销小适用场景树、分治、回溯简单重复计算二、递归的经典问题汉诺塔2.1 问题描述有三根柱子A、B、CA柱上有n个大小不同的圆盘大的在下小的在上。要求把所有圆盘从A移动到C每次只能移动一个圆盘且大圆盘不能放在小圆盘上面。求移动步骤。2.2 递归思路要把n个盘子从A移到C先把上面 n-1 个盘子从A移到B借助C把最大的盘子从A移到C再把 n-1 个盘子从B移到C借助Atext终止条件n 1 时直接移动2.3 代码实现c#include stdio.h // 汉诺塔递归实现 void hanoi(int n, char from, char to, char aux) { if (n 1) { printf(移动 1 号盘: %c - %c\n, from, to); return; } // 将 n-1 个盘子从 from 移到 aux hanoi(n - 1, from, aux, to); // 移动最大的盘子 printf(移动 %d 号盘: %c - %c\n, n, from, to); // 将 n-1 个盘子从 aux 移到 to hanoi(n - 1, aux, to, from); } int main() { int n 3; printf(汉诺塔 %d 个盘子移动步骤:\n, n); hanoi(n, A, C, B); return 0; }运行结果text汉诺塔 3 个盘子移动步骤: 移动 1 号盘: A - C 移动 2 号盘: A - B 移动 1 号盘: C - B 移动 3 号盘: A - C 移动 1 号盘: B - A 移动 2 号盘: B - C 移动 1 号盘: A - C复杂度移动次数 2ⁿ - 1时间复杂度 O(2ⁿ)三、分治法Divide and Conquer3.1 分治法的三步骤分治法将大问题分解成若干个相同的小问题递归解决后合并结果。步骤说明分解将原问题分解成若干个子问题解决递归解决子问题子问题足够小时直接解决合并将子问题的解合并成原问题的解3.2 典型应用算法分解合并时间复杂度归并排序分成两半合并两个有序数组O(n log n)快速排序按基准分区不需要合并O(n log n)二分查找取中间点不需要合并O(log n)汉诺塔分成n-1和1简单组合O(2ⁿ)最大子数组分成左右和跨中取最大值O(n log n)3.3 归并排序分治法经典c#include stdio.h #include stdlib.h // 合并两个有序子数组 void merge(int arr[], int left, int mid, int right, int temp[]) { int i left, j mid 1, k left; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; for (i left; i right; i) { arr[i] temp[i]; } } // 归并排序分治 void mergeSort(int arr[], int left, int right, int temp[]) { if (left right) return; // 终止条件只有一个元素 int mid left (right - left) / 2; // 分解 mergeSort(arr, left, mid, temp); mergeSort(arr, mid 1, right, temp); // 合并 merge(arr, left, mid, right, temp); } int main() { int arr[] {8, 3, 5, 1, 6, 2, 7, 4}; int n sizeof(arr) / sizeof(arr[0]); int *temp (int*)malloc(n * sizeof(int)); printf(原数组: ); for (int i 0; i n; i) printf(%d , arr[i]); printf(\n); mergeSort(arr, 0, n - 1, temp); printf(排序后: ); for (int i 0; i n; i) printf(%d , arr[i]); printf(\n); free(temp); return 0; }四、递归的优化尾递归与记忆化4.1 尾递归尾递归是指递归调用是函数的最后一个操作编译器可以优化为迭代避免栈溢出。c// 普通递归阶乘不是尾递归因为最后还有乘法 int factorial(int n) { if (n 1) return 1; return n * factorial(n - 1); } // 尾递归阶乘 int factorialTail(int n, int result) { if (n 1) return result; return factorialTail(n - 1, n * result); }4.2 记忆化递归避免重复计算斐波那契数列的普通递归有大量重复计算用记忆化优化。c#define MAX 100 int memo[MAX]; int fib(int n) { if (n 1) return n; if (memo[n] ! 0) return memo[n]; memo[n] fib(n - 1) fib(n - 2); return memo[n]; }版本时间复杂度说明普通递归O(2ⁿ)大量重复计算记忆化递归O(n)每个数只算一次迭代O(n)最优五、递归的常见陷阱5.1 栈溢出递归深度过大时系统栈空间耗尽。c// 递归深度10000可能导致栈溢出 void deepRecursion(int n) { if (n 0) return; deepRecursion(n - 1); }解决方案改用迭代增加栈大小编译器选项使用尾递归部分编译器优化5.2 重复计算斐波那契普通递归的重复计算问题。5.3 终止条件错误忘记终止条件或条件错误会导致无限递归。c// 错误n0时没有正确返回 int badFactorial(int n) { return n * badFactorial(n - 1); // n0时永远不停止 }六、递归与分治的应用场景场景推荐原因树/图的遍历递归结构天然适合递归排序归并/快排分治经典应用二分查找递归/迭代均可简单动态规划递归记忆化自顶向下思考回溯八皇后、迷宫递归需要状态恢复分治最大子数组递归分解合并清晰七、小结这一篇我们学习了递归与分治概念核心要点递归本质系统栈的压入与弹出递归要素终止条件 递推公式汉诺塔经典递归问题O(2ⁿ)分治法分解 → 解决 → 合并归并排序分治法的典型应用尾递归可被编译器优化为循环记忆化避免重复计算递归思考模板textfunction(问题): if (问题足够小): 直接解决 else: 分解成子问题 递归解决子问题 合并子问题的解下一篇我们讲动态规划。八、思考题递归函数的空间复杂度为什么等于递归深度汉诺塔问题中移动 n 个盘子需要多少步为什么如何判断一个问题适合用递归解决递归的缺点是什么用递归实现二分查找并分析其空间复杂度。欢迎在评论区讨论你的答案。