1. 递归题目训练2到底在练什么递归题目训练2这个标题看起来像是一个系列练习的第二阶段总结。如果你正在刷算法题或者带人入门数据结构与算法大概率会碰到这个阶段——第一轮递归训练让你理解了“函数自己调用自己”这件事第二轮则开始上强度把递归从“能写出来”逼到“写得对、写得快、写得稳”。我先说清楚这个内容适合谁看。如果你刚学完递归的基本写法能独立写出阶乘、斐波那契数列这种入门题但一遇到“递归加回溯”“递归加记忆化”“递归加剪枝”就卡壳那这篇总结就是给你写的。如果你已经能稳定做出中等难度的递归题但总是在边界条件、重复计算、递归深度这几个地方翻车这篇也能帮你把漏洞补上。如果你在准备技术面试递归类题目几乎是必考项第二轮训练的质量直接决定你在面试现场的发挥。递归题目训练2的核心目标我自己的理解是三个字建体系。第一轮训练是散点式的做一道会一道题目稍微变形就懵了。第二轮要把递归题目按“问题结构”分类每一类都有对应的思考框架和代码模板。比如“树形结构上的递归”和“数组子集上的递归”看起来都是递归但思考路径完全不同。前者关注节点与子树的关系后者关注“选或不选”的决策树。不把这两类分开练做再多题也是混的。还有一个容易被忽略的点递归题目训练2通常会引入复杂度分析的要求。第一轮你只要写出正确答案就行第二轮你得说清楚这个递归的时间复杂度是怎么算的。很多人在这一步栽跟头因为递归的复杂度不像循环那么直观需要画递归树、数节点、找重叠子问题。这个能力不练出来面试时被追问“你这个解法的时间复杂度是多少”就只能干瞪眼。从搜索热度来看递归题目训练2这个关键词背后大量的人在找“递归题目总结”“递归训练题单”“递归与回溯的区别”这类内容。说明大家在第一轮学完之后普遍需要一个系统化的梳理。我下面就把这个梳理做透从设计思路到实操细节再到踩坑记录全部展开。2. 递归训练第二阶段的整体设计思路2.1 为什么第一轮刷题效果不明显很多人第一轮递归训练的做法是找一份题单从“递归入门”开始刷两数相加、反转链表、二叉树遍历一路刷下去。刷了二三十道感觉自己会了。但过一周再回头看发现当时能写出来的题现在又不会了。问题出在哪我观察下来核心原因是没有建立递归的“状态意识”。递归函数的本质是一个状态机每次调用都在处理一个特定的状态。第一轮刷题时大多数人只关注“这个函数要做什么”不关注“这个函数接收什么状态、返回什么状态、状态之间怎么转移”。比如反转链表这道题递归函数的定义是“反转以head为起点的链表并返回新的头节点”。这个定义里包含了输入状态head和输出状态新头节点以及状态转移head.next的链表先反转再把head接到末尾。第一轮如果只背代码不理解这个状态定义换一道“反转链表的前N个节点”就写不出来了。第二轮训练的设计思路就是强制你在写代码之前先写出递归函数的定义。这个定义必须包含三要素输入是什么、输出是什么、这个函数做了什么。写不出这个定义说明你还没想清楚不要急着写代码。2.2 第二轮训练的四个核心模块我把递归题目训练2的内容拆成四个模块每个模块解决一类问题。这个拆法不是拍脑袋想的是根据递归题目的“问题结构”来的。第一个模块是线性递归处理数组、链表、字符串这类线性结构。核心思考框架是“当前元素处理完剩下的交给递归”。典型题目包括数组求和、链表反转、字符串反转、删除链表节点等。这个模块的关键是理解“递归方向”——是从前往后还是从后往前这决定了你的代码是在递归调用之前处理还是之后处理。第二个模块是树形递归处理二叉树、多叉树、图这类非线性结构。核心思考框架是“当前节点处理完左右子树分别递归”。典型题目包括二叉树遍历、求树的高度、判断平衡树、路径求和等。这个模块的关键是理解“递归的返回值怎么合并”——左右子树的结果怎么组合成当前节点的结果。第三个模块是决策递归也就是回溯。处理子集、排列、组合、棋盘问题这类“做选择”的场景。核心思考框架是“在每个节点做选择选完递归递归完撤销选择”。典型题目包括子集生成、全排列、组合求和、N皇后等。这个模块的关键是理解“选择与撤销”的对称性以及剪枝的时机。第四个模块是分治递归处理归并排序、快速排序、二分查找这类“分而治之”的场景。核心思考框架是“把问题分成子问题分别求解再合并”。典型题目包括归并排序、快速排序、二分搜索、大整数乘法等。这个模块的关键是理解“分”的边界和“合”的逻辑。这四个模块不是孤立的。树形递归里经常用到分治的思想决策递归里经常用到线性递归的遍历方式。但分开练的好处是每一类问题都有清晰的思考入口不会一上来就懵。2.3 复杂度分析为什么是第二阶段的重点第一轮训练时很多人写递归不考虑复杂度觉得“能跑就行”。但递归的复杂度分析是面试和实际工程中的硬要求。我举个例子斐波那契数列的朴素递归时间复杂度是O(2^n)因为递归树是指数级展开的。但加上记忆化之后复杂度降到O(n)因为每个子问题只算一次。这个优化过程如果不理解递归树的结构根本做不出来。第二轮训练要求你对每道题都做复杂度分析。具体做法是画出递归树数一数树上有多少个节点每个节点做了多少操作。节点数乘以单节点操作数就是总复杂度。如果发现递归树上有重复的子问题那就是记忆化的切入点。如果发现递归树退化成链表那就是递归深度过大的信号需要考虑改成迭代或者优化递归结构。这个能力练出来之后你看到一道递归题脑子里会自动浮现出递归树的形状复杂度分析就是数节点的事。面试时被问到复杂度你可以直接画图解释比背答案有说服力得多。3. 核心细节解析与实操要点3.1 递归函数的定义怎么写才不翻车写递归函数定义我总结了一个模板你直接套就行函数名(参数列表) - 返回值类型对[参数描述]执行[操作描述]并返回[返回值描述]。举个例子二叉树的最大深度maxDepth(TreeNode root) - int对以root为根的二叉树计算其最大深度并返回这个深度值。这个定义写出来之后代码几乎就是翻译def maxDepth(root): if root is None: return 0 left_depth maxDepth(root.left) right_depth maxDepth(root.right) return max(left_depth, right_depth) 1你看定义写清楚了代码就是自然推导出来的。反过来如果你写不出这个定义说明你还没想清楚这个递归要干什么这时候写代码就是瞎写。这里有个实操心得定义里的“返回值描述”要特别小心。很多递归题翻车就翻在返回值上。比如“判断平衡二叉树”这道题递归函数如果只返回“是否平衡”那你就没法判断当前节点是否平衡因为你需要知道左右子树的高度。所以正确的定义是返回以当前节点为根的子树高度如果发现不平衡就返回-1。这个定义里的返回值描述是“高度或-1”不是简单的“是否平衡”。定义写对了代码就对了。3.2 边界条件到底怎么设才不漏边界条件是递归题的第二大翻车点。我见过太多人代码逻辑都对就是边界条件漏了一个导致栈溢出或者死循环。边界条件的设置原则是覆盖所有不需要递归就能直接返回的情况。具体来说分三类第一类是空输入。数组为空、链表为空、树为空、字符串为空。这类边界通常返回一个“中性值”比如求和返回0求最大值返回负无穷求长度返回0。第二类是单元素输入。数组只有一个元素、链表只有一个节点、树只有一个节点。这类边界通常直接返回这个元素本身或者基于这个元素做简单计算。第三类是递归终止条件。比如二分查找中left right排列问题中当前路径长度等于数组长度。这类边界是递归“到底了”的信号需要根据题目要求返回结果或记录结果。我自己的做法是写完递归函数后拿一张纸把这三类边界各举一个例子手动模拟一遍。如果有一类边界模拟不通说明边界条件没设全。这个习惯帮我省了很多调试时间。注意边界条件的顺序很重要。通常先判断空输入再判断单元素最后判断递归终止。顺序错了可能导致空指针异常或者逻辑错误。3.3 递归方向前序、后序、还是中序递归方向决定了你在递归调用的前、中、后哪个位置处理当前节点。这个选择不是随意的取决于你的处理逻辑依赖什么。前序位置处理当前节点然后递归左右子树。适用于“从根到叶”的场景比如打印路径、传递参数给子树。前序位置的代码在进入子树之前执行。后序位置先递归左右子树然后处理当前节点。适用于“从叶到根”的场景比如计算子树的和、判断平衡、合并结果。后序位置的代码在子树返回之后执行。中序位置在递归左子树之后、递归右子树之前处理当前节点。主要用于二叉搜索树的有序遍历。我自己的经验是大部分递归题都是后序位置处理。因为你需要先拿到子树的结果才能计算当前节点的结果。前序位置通常用于“传递信息”比如把当前路径传给子树。中序位置比较特殊只在特定场景用。举个例子判断两棵二叉树是否相同。你需要先判断当前节点的值是否相同然后判断左右子树是否相同。这个逻辑是前序的先处理当前节点再递归子树。但如果你要计算两棵树是否“镜像对称”那就需要先递归左右子树再比较结果这是后序的。方向选错了代码逻辑就拧了。3.4 记忆化什么时候加怎么加记忆化是递归优化的第一把刀。但不是所有递归题都需要记忆化。判断标准很简单递归树上有重复子问题吗怎么判断有没有重复子问题画递归树。如果不同的递归路径到达了相同的状态那就是重复子问题。比如斐波那契数列f(5)会调用f(4)和f(3)f(4)又会调用f(3)和f(2)f(3)被算了两次。这就是重复子问题。记忆化的实现方式有两种自顶向下的备忘录和自底向上的动态规划。第二轮训练主要练自顶向下的备忘录因为它的结构和递归完全一致只是在递归函数开头加一个“查表”操作在返回之前加一个“写表”操作。def fib(n, memo{}): if n in memo: return memo[n] if n 1: return n memo[n] fib(n-1, memo) fib(n-2, memo) return memo[n]这个模板的关键是查表要在边界判断之前。因为边界条件的结果也可能被重复计算先查表可以省掉重复的边界判断。另外memo的key要能唯一标识一个子问题通常用参数组合作为key。注意记忆化不是万能的。如果递归树上的状态空间太大备忘录会占用大量内存。这时候需要考虑自底向上的动态规划或者优化状态表示。3.5 回溯的“选择-递归-撤销”三步曲回溯是递归题目训练2的重头戏。很多人觉得回溯难其实回溯的代码结构非常固定就是三步做选择、递归、撤销选择。def backtrack(path, choices): if 满足终止条件: 记录结果 return for choice in choices: 做选择 backtrack(path, 新的choices) 撤销选择这个结构看起来简单但实操中有几个细节容易翻车。第一个细节是选择列表的更新。有些题目的选择列表在递归过程中会变化比如组合求和问题选了一个数之后后面的选择只能从当前索引之后选。这时候需要传递一个start参数来控制选择范围。第二个细节是撤销操作的对称性。做了选择之后递归返回时必须撤销而且撤销的操作必须和选择的操作完全对称。比如选择时path.append(choice)撤销时就必须path.pop()。如果选择时修改了多个变量撤销时也要恢复多个变量。第三个细节是剪枝的时机。剪枝可以在做选择之前也可以在递归调用之前。通常在做选择之前剪枝效率更高因为可以避免无效的递归调用。比如组合求和问题如果当前和已经超过目标值就不需要继续选了。我自己的经验是回溯题先写不剪枝的版本跑通之后再加剪枝。一上来就想着剪枝很容易把逻辑搞乱最后连正确答案都出不来。4. 实操过程与核心环节实现4.1 线性递归实操以链表反转为例链表反转是线性递归的经典题。题目要求把单链表反转返回新的头节点。先写递归函数定义reverseList(ListNode head) - ListNode反转以head为起点的链表返回反转后的新头节点。这个定义的关键是“以head为起点”意味着递归调用时传入的是head.next返回的是反转后的新头节点。边界条件head为空或head.next为空时直接返回head。因为空链表反转还是空单节点链表反转还是自己。递归逻辑先反转head.next为起点的链表得到新头节点newHead。然后把head接到反转后链表的末尾。具体操作是head.next.next head然后head.next None。def reverseList(head): if head is None or head.next is None: return head new_head reverseList(head.next) head.next.next head head.next None return new_head这段代码的实操要点head.next.next head这一步是把当前节点接到反转后链表的末尾。因为反转后head.next变成了新链表的尾节点所以head.next.next就是尾节点的next指针把它指向head就把head接上去了。然后head.next None断开原来的连接防止成环。复杂度分析递归深度是链表长度n每层递归做常数次操作所以时间复杂度O(n)空间复杂度O(n)递归栈。注意链表反转的递归写法在实际工程中不常用因为递归栈有溢出风险。工程中更常用迭代写法。但作为递归思维的训练这道题非常典型。4.2 树形递归实操以二叉树最近公共祖先为例最近公共祖先LCA是树形递归的经典题。题目要求找到二叉树中两个节点的最近公共祖先。递归函数定义lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) - TreeNode在以root为根的二叉树中找到p和q的最近公共祖先并返回这个节点。边界条件root为空时返回None。root等于p或q时返回root。因为如果当前节点就是p或q那它本身就是最近公共祖先或者最近公共祖先在它上面但递归返回时上层会处理。递归逻辑分别递归左右子树得到left和right。如果left和right都不为空说明p和q分别在左右子树中当前root就是最近公共祖先。如果只有left不为空说明p和q都在左子树中返回left。如果只有right不为空返回right。def lowestCommonAncestor(root, p, q): if root is None or root p or root q: return root left lowestCommonAncestor(root.left, p, q) right lowestCommonAncestor(root.right, p, q) if left and right: return root return left if left else right这段代码的实操要点递归函数的返回值不是简单的“找到了”或“没找到”而是“找到了就返回那个节点没找到就返回None”。这个返回值设计让上层可以判断p和q的分布情况。复杂度分析每个节点访问一次时间复杂度O(n)。递归深度是树的高度最坏情况O(n)平均O(log n)。注意LCA问题有一个变种是“二叉搜索树的LCA”可以利用BST的有序性把复杂度降到O(log n)。但普通二叉树的LCA只能用上面的递归解法。4.3 决策递归实操以全排列为例全排列是决策递归的经典题。题目要求生成一个数组的所有排列。递归函数定义backtrack(path, used)当前已经选了path中的元素used标记了哪些元素已经被选生成所有可能的排列并记录到结果中。边界条件path的长度等于数组长度时说明已经选完了把path加入结果集。递归逻辑遍历数组中的每个元素如果该元素没有被使用过就把它加入path标记为已使用然后递归。递归返回后把它从path中移除标记为未使用。def permute(nums): result [] used [False] * len(nums) def backtrack(path): if len(path) len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] True path.append(nums[i]) backtrack(path) path.pop() used[i] False backtrack([]) return result这段代码的实操要点result.append(path[:])这里必须用path的拷贝不能直接append(path)。因为path在后续的递归中会被修改如果直接append引用最后result里的所有元素都会变成同一个空列表。复杂度分析排列数是n!每个排列需要O(n)的时间复制到结果集所以时间复杂度O(n * n!)。空间复杂度O(n)递归栈和path。注意全排列问题如果有重复元素需要先排序然后在递归时跳过重复元素。跳过条件是i 0 and nums[i] nums[i-1] and not used[i-1]。这个条件的意思是如果当前元素和前一个元素相同且前一个元素没有被使用说明这是同一层递归中的重复选择跳过。4.4 分治递归实操以归并排序为例归并排序是分治递归的经典题。题目要求对一个数组进行排序。递归函数定义mergeSort(nums, left, right)对nums数组中[left, right]区间的元素进行排序。边界条件left right时区间只有一个元素或为空不需要排序直接返回。递归逻辑计算中点mid分别对[left, mid]和[mid1, right]进行排序然后合并两个有序区间。def mergeSort(nums, left, right): if left right: return mid (left right) // 2 mergeSort(nums, left, mid) mergeSort(nums, mid1, right) merge(nums, left, mid, right) def merge(nums, left, mid, right): temp [] i, j left, mid1 while i mid and j right: if nums[i] nums[j]: temp.append(nums[i]) i 1 else: temp.append(nums[j]) j 1 while i mid: temp.append(nums[i]) i 1 while j right: temp.append(nums[j]) j 1 nums[left:right1] temp这段代码的实操要点merge操作是归并排序的核心。合并两个有序区间时需要额外的临时数组。合并完成后把临时数组的内容复制回原数组的对应位置。复杂度分析递归树的高度是log n每层合并操作的总时间是O(n)所以时间复杂度O(n log n)。空间复杂度O(n)临时数组和递归栈。注意归并排序的递归写法中mid的计算要用(left right) // 2不能用(left right) / 2。另外递归终止条件是left right不是left right。这两个细节搞错了会导致死循环或数组越界。5. 常见问题与排查技巧实录5.1 递归栈溢出怎么排查和解决递归栈溢出是递归题最常见的运行时错误。表现是程序抛出“RecursionError: maximum recursion depth exceeded”或者直接崩溃。排查思路分三步第一步确认递归深度是否真的超过了限制。Python默认的递归深度限制是1000可以通过sys.setrecursionlimit()调整。但调整限制只是治标治本还是要优化递归结构。第二步检查递归终止条件是否覆盖了所有情况。最常见的栈溢出原因是终止条件漏了某个分支导致递归无限进行。比如二叉树遍历时只判断了root is None没有判断root.left is None和root.right is None虽然最终也会终止但多了一层不必要的递归。第三步检查递归是否在“原地打转”。有些递归题的状态转移设计有问题导致递归调用没有向终止条件靠近。比如二分查找中mid的计算如果写错了可能导致left和right不变递归永远不终止。解决栈溢出的方法有几种一是优化递归结构减少递归深度二是改成迭代写法用显式栈代替递归栈三是加记忆化避免重复递归四是调整递归深度限制临时方案。注意调整递归深度限制有风险可能导致真正的栈溢出C栈溢出程序直接崩溃而不是抛出异常。生产环境中慎用。5.2 重复计算怎么识别和消除重复计算是递归性能问题的头号原因。识别方法是画递归树看有没有相同的状态被多次计算。以斐波那契数列为例朴素递归的递归树中f(3)被计算了多次。消除方法是加备忘录把已经计算过的结果存起来下次直接取。但有些题的重复计算不那么明显。比如“不同路径”问题机器人从左上角走到右下角每次只能向右或向下。朴素递归的递归树中(m, n)位置被多次到达。消除方法是用一个二维数组memo记录每个位置的结果。识别重复计算的一个技巧是看递归函数的参数组合是否有限。如果参数组合是有限的比如数组索引、坐标、剩余容量那就可以用备忘录。如果参数组合是无限的比如浮点数、字符串那就不适合用备忘录。注意备忘录的key要能唯一标识一个子问题。对于多参数的情况可以用元组作为key或者把参数编码成一个整数。5.3 回溯结果重复怎么去重回溯题的结果重复通常有两个原因一是选择列表中有重复元素二是选择顺序不同但结果相同。对于第一种情况去重方法是先排序然后在递归时跳过重复元素。跳过条件是当前元素和前一个元素相同且前一个元素没有被使用。这个条件保证了同一层递归中相同的元素只会被选择一次。对于第二种情况去重方法是限制选择顺序。比如组合问题中用start参数控制选择范围保证每个元素只被选择一次且选择顺序是递增的。这样就不会出现[1,2]和[2,1]这种重复组合。我自己的经验是回溯去重先排序再在递归循环中加跳过条件。排序是为了让相同元素相邻跳过条件是为了避免同一层递归中的重复选择。这两个操作配合使用能解决大部分去重问题。5.4 递归转迭代的通用方法有些场景下递归写法会栈溢出或者性能不够好需要转成迭代写法。递归转迭代的通用方法是用显式栈模拟递归调用栈。具体做法是把递归函数的参数打包成一个状态对象压入栈中。然后循环从栈中弹出状态处理状态把新的状态压入栈中。直到栈为空。以二叉树前序遍历为例递归写法是def preorder(root): if root is None: return print(root.val) preorder(root.left) preorder(root.right)迭代写法是def preorder(root): if root is None: return stack [root] while stack: node stack.pop() print(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left)注意迭代写法中先压右子树再压左子树这样弹出时就是先左后右符合前序遍历的顺序。注意递归转迭代不是所有场景都值得做。如果递归深度不大递归写法更简洁易读。只有在递归深度可能很大或者性能要求很高的场景下才考虑转迭代。5.5 常见问题速查表问题现象可能原因排查方法解决方案栈溢出终止条件漏了检查所有分支是否都有终止条件补全终止条件栈溢出递归深度过大打印递归深度转迭代或加记忆化结果错误边界条件不对手动模拟边界情况修正边界条件结果错误递归方向不对检查处理逻辑在递归前还是后调整处理位置结果重复选择列表有重复检查输入是否有重复元素排序后跳过重复结果重复选择顺序不同检查是否限制了选择顺序加start参数超时重复计算画递归树看有无重复状态加备忘录超时剪枝不够检查是否有无效分支加剪枝条件内存超限备忘录太大检查状态空间大小优化状态表示或转DP这张表是我自己刷题时总结的基本上覆盖了递归题90%以上的问题。遇到问题时先查表能快速定位原因。6. 递归训练第二阶段的进阶建议6.1 怎么从“会写”到“写得好”会写递归和写得好递归是两回事。会写是指能写出正确答案写得好是指代码简洁、边界清晰、复杂度优、可读性强。从会写到写得好我自己的经验是三个字多回头看。每做完一道题隔一天再回来看自己的代码问自己三个问题这个递归函数的定义能不能更清晰边界条件能不能更简洁有没有重复计算可以消除还有一个方法是对比别人的解法。同一道题不同人的递归写法可能差异很大。看别人的代码时重点关注他们的递归函数定义和边界条件处理。有时候别人的一个巧妙定义能让代码简洁一半。6.2 递归思维在实际工程中的应用递归思维不只是刷题用的。实际工程中很多场景都用到递归思维。比如处理嵌套的JSON数据、遍历文件目录树、解析HTML DOM树、实现表达式求值等。这些场景的共同特点是数据结构本身是递归定义的树、图、嵌套结构所以处理逻辑也应该是递归的。掌握递归思维能让你在面对这些场景时快速找到解法。我自己的体会是递归思维的核心是“把大问题分解成同构的小问题”。这个思维方式不仅适用于算法题也适用于系统设计、项目管理等场景。把一个复杂系统分解成多个同构的子系统每个子系统用相同的逻辑处理这就是递归思维在工程中的应用。6.3 后续练习方向递归题目训练2完成之后下一步可以往两个方向走。一个是动态规划因为动态规划和递归加记忆化本质上是同一件事的两种表达。掌握了递归加记忆化动态规划的状态转移方程就很容易推导出来。另一个方向是图论算法因为图的遍历DFS、BFS本质上就是递归和队列的应用。掌握了树形递归图的DFS就很容易上手。我自己的练习路径是递归训练2完成后先刷20道动态规划题再刷20道图论题。这个路径走下来递归思维就彻底内化了遇到新题能快速识别出“这是递归题”还是“这是DP题”还是“这是图论题”。最后分享一个小技巧每天花10分钟默写递归模板。线性递归、树形递归、决策递归、分治递归每个模板默写一遍。坚持两周你会发现写递归题时手速快了很多因为模板已经刻在肌肉记忆里了。这个习惯我从训练第二阶段开始保持到现在还在用效果非常好。