【程序员必学】20天从零到一学算法系列：第四篇：递归与分治——把大问题拆成小问题

写在最前有些问题天生适合“自己调用自己”——这就是递归。而分治则是一种更宏大的策略将大问题拆成几个相同的小问题分别解决再合并结果。本文从零讲解递归三要素、分治模板并通过归并排序让你彻底理解“分而治之”。建议收藏反复查阅。1. 什么是递归定义一个函数在它的定义中直接或间接调用自身称为递归。生活中的例子俄罗斯套娃打开一个娃娃里面还有一个更小的娃娃……电影《盗梦空间》梦中还有梦直到回到现实。递归的三个关键要素重要终止条件Base Case什么时候不再调用自己直接返回结果。没有终止条件 → 无限递归 → 栈溢出。递推公式Recurrence Relation如何把当前问题分解成更小的同类问题。返回值每一层把子问题的结果处理后返回给上一层。示例计算 n 的阶乘n! 1×2×3×…×n终止条件n 1 时返回 1递推公式n! n × (n-1)!返回值n × 子问题的结果2. 递归代码示例2.1 阶乘Python JavaPythondeffactorial(n):# 终止条件ifn1:return1# 递推公式returnn*factorial(n-1)print(factorial(5))# 输出: 120JavapublicclassMain{publicstaticintfactorial(intn){if(n1)return1;returnn*factorial(n-1);}publicstaticvoidmain(String[]args){System.out.println(factorial(5));// 输出: 120}}执行过程以 factorial(3) 为例factorial(3) 3 * factorial(2) 3 * (2 * factorial(1)) 3 * (2 * 1) 62.2 斐波那契数列低效版理解递归树斐波那契数列F(0)0, F(1)1, F(n)F(n-1)F(n-2)Pythondeffib(n):ifn1:returnnreturnfib(n-1)fib(n-2)print(fib(6))# 输出: 8问题这个写法存在大量重复计算fib(2) 被算了多次。复杂度 O(2ⁿ)极慢。改进方法记忆化Memoization—— 用一个字典/数组保存已经算过的结果。deffib_memo(n,memo{}):ifninmemo:returnmemo[n]ifn1:returnn memo[n]fib_memo(n-1,memo)fib_memo(n-2,memo)returnmemo[n]print(fib_memo(40))# 瞬间算出记忆化后的时间复杂度 O(n)空间复杂度 O(n)。3. 分治思想定义分治Divide and Conquer是一种算法设计策略分为三步分解Divide将原问题分成若干个规模更小的相同子问题。解决Conquer递归地解决每个子问题。如果子问题足够小直接解决。合并Combine将子问题的结果合并成原问题的解。分治与递归的关系分治通常用递归实现但递归只是一种编程技巧分治是一种更宏观的策略。经典例子归并排序快速排序二分查找可以看作分治的特例4. 归并排序分治的典型归并排序的思路先把数组分成两半分别排好序再把两个有序数组合并成一个有序数组。很多初学者卡在“合并”这一步。下面我们先不用代码先用数字一步一步模拟。4.1 举个例子对[38, 27, 43, 3, 9, 82, 10]排序第一步分解不断从中间切分把数组一直切分成单个元素单个元素天然有序。[38, 27, 43, 3, 9, 82, 10] / \ [38, 27, 43, 3] [9, 82, 10] / \ / \ [38, 27] [43, 3] [9, 82] [10] / \ / \ / \ | [38][27] [43][3] [9][82] [10]第二步合并重点从最底层开始把两个有序的小数组合并成一个大的有序数组。合并第1对[38]和[27]准备一个空数组result。比较两个数组的第一个元素38 和 27 → 27 更小取出 27 放入resultresult [27]。左侧数组还有[38]右侧数组已空。把左侧剩余的[38]直接追加到result后面 →result [27, 38]。结果[27, 38]合并第2对[43]和[3]比较 43 和 3 → 3 小取出 3 →[3]左侧还有[43]追加 →[3, 43]结果[3, 43]合并第3对[9]和[82]比较 9 和 82 → 9 小取出 9 →[9]追加剩余[82]→[9, 82]结果[9, 82]第4对只有一个[10]没有合并对象暂时保留为[10]。现在上一层变成[27, 38] [3, 43] [9, 82] [10]合并[27, 38]和[3, 43]重点中的重点两个有序数组左 [27, 38]右 [3, 43]。我们要把它们合并成一个有序数组。创建空result []两个指针i 指向左数组开头27j 指向右数组开头3第1步比较 27 和 3 → 3 小把 3 放入 resultj 右移到 43。result [3]第2步比较 27 和 43 → 27 小把 27 放入 resulti 右移到 38。result [3, 27]第3步比较 38 和 43 → 38 小把 38 放入 resulti 移动左数组已空。result [3, 27, 38]第4步左数组已空把右数组剩下的[43]直接追加到 result 末尾。result [3, 27, 38, 43]完成得到了[3, 27, 38, 43]。合并[9, 82]和[10]左 [9, 82]右 [10]result []i 指向 9j 指向 10比较 9 和 10 → 9 小取 9i 移到 82result [9]比较 82 和 10 → 10 小取 10j 移出右数组空result [9, 10]左数组还剩[82]追加 →result [9, 10, 82]结果[9, 10, 82]现在数组变成[3, 27, 38, 43] [9, 10, 82]最后一次合并[3, 27, 38, 43]和[9, 10, 82]左 [3, 27, 38, 43]右 [9, 10, 82]result []i 指向 3j 指向 93 9 → 取 3i → 27[3]27 9? 否 → 取 9j → 10[3, 9]27 10? 否 → 取 10j → 82[3, 9, 10]27 82 → 取 27i → 38[3, 9, 10, 27]38 82 → 取 38i → 43[3, 9, 10, 27, 38]43 82 → 取 43i 移出左数组空[3, 9, 10, 27, 38, 43]右数组剩余[82]追加 →[3, 9, 10, 27, 38, 43, 82]排序完成4.2 合并两个有序数组的通用步骤伪代码defmerge(left,right):result[]i0# left 的指针j0# right 的指针# 当两个数组都还有元素时whileilen(left)andjlen(right):ifleft[i]right[j]:result.append(left[i])i1else:result.append(right[j])j1# 如果 left 还有剩余全部追加whileilen(left):result.append(left[i])i1# 如果 right 还有剩余全部追加whilejlen(right):result.append(right[j])j1returnresult关键理解因为 left 和 right 各自已经是有序的所以每次只需比较它们当前指针指向的元素谁小谁先出去。当一个数组被取完另一个数组剩下的元素一定比结果中所有元素都大或相等直接全部追加即可。4.3 归并排序的完整代码带详细注释Pythondefmerge_sort(arr):# 终止条件数组长度 1 时已经有序iflen(arr)1:returnarr# 1. 分解从中间切分midlen(arr)//2leftmerge_sort(arr[:mid])# 递归排序左半rightmerge_sort(arr[mid:])# 递归排序右半# 2. 合并把两个有序数组合并returnmerge(left,right)defmerge(left,right):result[]i,j0,0# 同时遍历两个数组whileilen(left)andjlen(right):ifleft[i]right[j]:result.append(left[i])i1else:result.append(right[j])j1# 剩余元素result.extend(left[i:])result.extend(right[j:])returnresult# 测试arr[38,27,43,3,9,82,10]sorted_arrmerge_sort(arr)print(sorted_arr)# [3, 9, 10, 27, 38, 43, 82]Javaimportjava.util.Arrays;publicclassMergeSort{publicstaticint[]mergeSort(int[]arr){if(arr.length1)returnarr;intmidarr.length/2;int[]leftmergeSort(Arrays.copyOfRange(arr,0,mid));int[]rightmergeSort(Arrays.copyOfRange(arr,mid,arr.length));returnmerge(left,right);}privatestaticint[]merge(int[]left,int[]right){int[]resultnewint[left.lengthright.length];inti0,j0,k0;while(ileft.lengthjright.length){if(left[i]right[j])result[k]left[i];elseresult[k]right[j];}while(ileft.length)result[k]left[i];while(jright.length)result[k]right[j];returnresult;}publicstaticvoidmain(String[]args){int[]arr{38,27,43,3,9,82,10};int[]sortedmergeSort(arr);System.out.println(Arrays.toString(sorted));}}5. 递归与分治的复杂度分析递归深度递归函数调用自身的最大层数。阶乘的递归深度为 n归并排序的递归深度为 log n。空间复杂度每次递归调用会占用栈空间。深度为 n 的递归可能导致栈溢出Python 默认约 1000 层。时间复杂度可通过递归树或主定理Master Theorem分析。示例归并排序的时间复杂度推导设 T(n) 为对 n 个元素排序的时间。分解为两个子问题每个 T(n/2)。合并两个有序数组需要 O(n)。所以 T(n) 2T(n/2) O(n)。解得 T(n) O(n log n)。6. 练习题推荐带 LeetCode 链接爬楼梯LeetCode 70 —— 本质是斐波那契练习递归和记忆化。反转链表递归版LeetCode 206 —— 理解递归如何“回头”。归并排序手动实现一次不依赖内置排序。汉诺塔LeetCode 面试题 08.06 —— 经典递归问题。7. 思考题递归和循环迭代之间如何互相转换什么时候适合用递归什么是“尾递归”为什么有些语言能优化尾递归而 Python 不能归并排序的合并过程为什么需要额外数组能否原地合并8. 小结要点说明递归三要素终止条件、递推公式、返回值分治三步分解 → 解决递归 → 合并归并排序典型分治时间 O(n log n)空间 O(n)记忆化解决重复子问题将指数级降为多项式级注意事项递归深度过大可能栈溢出可改用迭代递归像一面镜子照出问题的自相似性分治则是用这面镜子把大问题碎成小块逐一击破。掌握递归和分治你就能解决一大类复杂问题。下一篇预告基础排序——冒泡、选择、插入排序。我们将手写这三种 O(n²) 排序并分析它们的稳定性与优化思路。非常感谢您的阅读整理不易如果喜欢请点赞、评论、收藏、关注哦您是最棒的