1. 整体思路拆解为什么这三个题值得一起刷这几天在题库里连续刷了三道基础题题号挨着内容也从DFS到递归再到递归变体刚好踩在一条非常典型的学习路径上。这三道题分别是“我素故我在深度优先搜索-基础题127th”、“汉诺塔问题的第m步递归-基础题128th”、“数字游戏递归-基础题129th”。单独看每一道都很简单但它们放在一起恰恰构成了一条从“理解递归”到“会用递归”再到“用DFS解决实际问题”的完整链路。先说“我素故我在”这道题。题目名字谐音笛卡尔的“我思故我在”但这里把“思”换成了“素”一看就知道和素数有关。实际题目内容是给定N个数字从中选出若干数字排列成一个序列要求相邻两数之和为素数然后输出所有满足条件的排列。这就是典型的深度优先搜索问题本质上是全排列加素数判断的杂交体。DFS在这里做的核心事情是维护一个当前路径尝试把每一个还没用过的数字放到下一个位置检查是否和上一个数字的和构成素数如果满足就继续深入不满足就剪枝回溯。“汉诺塔问题的第m步”看起来和DFS没关系但它考察的是递归的底层执行顺序。普通版本的汉诺塔题目一般只要求输出总步数或者完整的移动过程这道题直接问你整个移动过程中第m步到底移动的是哪块盘子、从哪个柱子移到哪个柱子。这就不只是会写递归就行的了你得真正理解递归栈每一层在干什么。很多同学能背出汉诺塔的递归代码但要它说出第m步做了什么就卡住了。原因在于对递归调用顺序缺乏具象化理解。第三道“数字游戏”又把递归换了个玩法。这类题典型的设定是给出一个数字串让你在数字之间插入运算符使等式成立或者给你一组数字通过加减乘除凑出目标值。用递归去做就是枚举每一种可能的组合方式本质上也是一个搜索过程只不过搜索空间是运算符和括号的分布。这三题连起来看结论很清楚递归是DFS的基础DFS是递归的应用延伸。搞清楚递归的执行顺序才谈得上理解回溯和剪枝理解了回溯才能写好DFS去解决排列、组合、路径搜索一类的问题。下面我把每道题的细节拆开讲。2. 逐题拆解三题背后的核心考点2.1 “我素故我在”DFS全排列 素数判定的组合拳先说判定方式。N一般不超过10数字范围也不大直接用最简单的试除法判断素数就够用了。从2循环到sqrt(x)只要存在一个能整除的因子就说明不是素数。这个判断在DFS的每一层都会调用次数不会太多性能压力可忽略。def is_prime(x): if x 2: return False i 2 while i * i x: if x % i 0: return False i 1 return TrueDFS的框架其实就是标准全排列模板套一个相邻和校验def dfs(path, used): if len(path) n: # 输出一个合法排列 print(path) return for i in range(n): if used[i]: continue # 剪枝若path非空且与上一个数之和不是素数跳过 if path and not is_prime(path[-1] nums[i]): continue used[i] True path.append(nums[i]) dfs(path, used) path.pop() used[i] False这里的关键在剪枝时机。只要当前候选数字与路径末尾数字之和不是素数就可以直接跳过完全不需要继续深入。递归层数是固定的N每一层的分支最多是N最坏复杂度是O(N!)。N取8到10时规模还能接受超过12就明显吃力了。这道题真正的考点不是性能优化而是DFS状态管理——used数组标记哪些数字已经用过递归回来之后要记得恢复现场。这道题里最容易踩的坑有两个第一个题目要求输出排列顺序不同题目可能要求字典序所以你遍历数字的顺序要先排好序否则结果顺序不对。第二个它要求的是相邻两个数字之和为素数不是所有数字之和有不少人一开始理解错写成了整条路径的和判断结果输出怎么都不对。2.2 汉诺塔第m步递归执行顺序的具象化考察汉诺塔的递归实现本身不难核心就三句话把上面n-1个盘子从A借助C移到B把最底下第n个盘子从A移到C把B上的n-1个盘子借助A移到C。代码写出来是def hanoi(n, src, aux, dst): if n 1: print(fmove disk 1 from {src} to {dst}) return hanoi(n - 1, src, dst, aux) print(fmove disk {n} from {src} to {dst}) hanoi(n - 1, aux, src, dst)但题目问你第m步移动的是什么就不能只print了。你需要把“步数”变成一个可以传递和累加的计数器。最简单的做法是设置一个全局计数器每次执行移动操作时步数加1当步数等于m时记录当前操作。但这有个问题——如果只是记录而不剪枝整个递归会全部跑完效率很低。更好的做法是在递归函数里传入目标步数m然后根据当前累计步数提前终止。更推荐一种不用全局变量的写法递归函数返回当前子树包含的移动步数主调方通过比较m和左侧子树的步数来决定进入哪个分支。具体思路是n个盘子的汉诺塔总步数为2^n - 1。注意第m步一定落在三个区段之一若m等于2^(n-1)那么第m步恰好是“把第n个盘子从源柱移到目标柱”若m小于2^(n-1)说明第m步在把上面n-1个盘子从源柱移到辅助柱的过程中递归处理规模n-1的子问题若m大于2^(n-1)说明第m步在把n-1个盘子从辅助柱移到目标柱的过程中此时需要把m减去2^(n-1)再递归这就是利用汉诺塔递归结构的数学性质直接定位第m步。不需要逐帧模拟时间复杂度从O(2^n)降到了O(n)。这也是这道题最漂亮的地方递归的理解深度直接影响算法设计水平。如果你只是逐条模拟移动当n稍大比如20甚至302^n步全跑一遍是跑不动的但用数学定位n1000都秒出答案。def find_mth_move(n, m, src, aux, dst): if n 1: return fmove disk 1 from {src} to {dst} half 1 (n - 2) # 2^(n-2)上面n-1个盘子移动总步数的一半 if m half 1: return fmove disk {n} from {src} to {dst} elif m half: return find_mth_move(n - 1, m, src, dst, aux) else: return find_mth_move(n - 1, m - half - 1, aux, src, dst)注意这里half的计算上面n-1个盘子移动的总步数是2^(n-1)-1所以中间那次大盘子移动是第2^(n-1)步即half1half2^(n-1)-1。哨兵判断m与2^(n-1)的关系即可。我在实际写的时候踩过一个非常隐蔽的坑边界溢出。有人会用1 (n - 2)去表示一半步数但当n1时n-2为负移位运算就出问题了。所以函数开头必须先处理n1的基准情形再进行half计算。2.3 数字游戏递归枚举的变式应用“数字游戏”这道题的题目描述一般有两种变体。一种是给你一串数字要求在所有相邻数字之间插入加号或减号使整个表达式的结果等于目标值另一种是给你几个数字通过加减乘除和括号运算得到目标值。不管是哪种核心都是递归枚举。以插入运算符的版本为例给定一个由数字组成的字符串在数字之间插入“”、“-”或不插入合并数字要求表达式结果为target。这个问题的递归思路是从左到右扫描字符串维护两个关键状态——当前位置索引pos以及当前表达式累计值cur。每一层递归处理从pos开始截取一段数字然后决定在这段数字前面加什么运算符。def dfs(pos, cur, expr): if pos len(s): if cur target: res.append(expr) return for end in range(pos 1, len(s) 1): num_str s[pos:end] if len(num_str) 1 and num_str[0] 0: continue # 跳过前导零 num int(num_str) if pos 0: dfs(end, num, num_str) else: dfs(end, cur num, expr num_str) dfs(end, cur - num, expr - num_str)这个递归和DFS本质上同构每一层递归展开多个分支每个分支对应一种选择整个递归树就是所有可能的表达式组合。剪枝在这里同样重要遇到前导零的数字段直接跳过避免出现“01”这种非法数字串还可以结合当前已经算出的cur和目标值的差距做粗略剪枝但数字范围较小的时候不剪枝也能过。另一种“给定数字凑目标值”的版本用递归做更经典每次从数字集合中取出两个数尝试加减乘除四种运算把结果放回集合中继续递归直到集合只剩一个数判断是否等于目标值。这个写法的关键还是“恢复现场”——每次递归返回后要把拿出去的两个数放回集合把产生的新数删掉。很多人卡在这一步忘记恢复现场导致集合越删越少。这类题想考察的核心能力有两个一是把问题拆解成“规模更小的同类问题”的能力二是枚举所有可能分支时对状态的管理能力。理解了DFS的人写数字游戏会非常顺手因为它们没有任何本质区别。3. 从递归到DFS一个更通用的思维模型3.1 递归的执行顺序分为“进入”和“返回”很多初学者对递归的理解停留在“函数自己调自己”这个层面一到写出bug的时候就说“递归太抽象了”。其实递归真正需要理解的是它的执行顺序每次递归调用都会先把当前函数的执行状态压入调用栈然后进入子调用子调用返回后再恢复之前的执行状态继续向下走。所以一个递归函数的执行流程不是一条直线而是一棵树的遍历。汉诺塔第m步那道题本质上就是在考察你是否理解这棵递归树的遍历顺序。以三个盘子为例移动顺序是先把上面2个盘子从A移到B再把第3个盘子从A移到C最后把B上的2个盘子移到C。整个过程中“移动第3个盘子”这一步恰好发生在整棵递归树的中间位置。推广到n个盘子第n个盘子的移动恰好也是所有步数中最中间的那一步。用这个树形结构去理解DFS就非常自然了DFS就是在一棵决策树上做深度优先遍历每深入一层就做一个选择走到叶子节点时记录结果然后回溯到上一层尝试其他选择。递归函数里的每个状态变量比如当前路径path、已用标记used就是树节点上保存的现场信息。3.2 剪枝的本质是跳过无效分支DFS最让人头疼的是复杂度——比如全排列是O(N!)不剪枝容易超时。但剪枝的本质只是提前判断某个分支有没有可能通向合法结果如果不可能就跳过。这个判断越强剪枝效果越好。拿“我素故我在”来说判断相邻两数之和是否为素数是在每一层选取下一个数字时做的。如果和为合数立刻跳过。这个剪枝看似简单实际效果惊人——当N10时全排列有三百多万种加了这个剪枝能砍掉大量无效分支。为什么素数在2到20之间的分布密度不算高相邻和为合数的概率远大于为素数所以大部分分支在第一层就被砍掉了。剪枝的思想在数字游戏里同样适用。比如已知所有剩余数字都是正数当前和已经大于目标值就不用再尝试加号分支了比如除法运算要检查除数是否为零比如当前数字串过长已经超过剩余长度能组成的最大数……这些判断有的很微小有的很关键但共同点是它们都是利用问题本身的性质在递归树更浅的位置上截断无效路径。3.3 从递归到非递归理解栈的显式使用刷完这三题之后如果觉得递归已经掌握了我建议再往前走一步把递归改成显式栈的迭代写法。这不仅是热词里提到的“快速排序非递归”那一类面试问题的准备更是对递归执行过程的一次彻底检验。递归是建立在系统调用栈上的系统帮你压栈、出栈。非递归写法就是把“当前节点状态”抽象成一个自定义结构体用显式的栈来模拟这个过程。还是拿DFS全排列举例非递归写法需要自己保存三个信息当前路径、当前可使用的数字集合、当前尝试到第几个数字。每次循环要么往前走一步尝试下一个数字要么往回退一步弹出栈顶恢复状态。这个过程写出来会比递归长不少但思路清晰度完全不同。当你亲手模拟了栈的压入弹出之后再回看递归就明白那句“递归就是隐式栈”是什么意思了。我当时练这个从递归到非递归的转换大概花了半天时间收获非常大。改写了汉诺塔的递归为栈模拟后再去解答“第m步”这个问题理解又深了一层——你甚至可以理解为递归解法本身就是在栈上进行DFS而汉诺塔三根柱子上的移动规律只是DFS决策树的具象化。4. 实操中的常见问题与排错心得4.1 全局变量与现场恢复DFS包括数字游戏这类递归枚举最常见的bug就是现场恢复不彻底。以全排列为例进入递归前你把数字加入path、标记used[i]True返回后必须path.pop()、used[i]False。少写任何一行都会导致后续分支状态错乱且这种错乱往往不报错只会给出错误的输出结果——排查起来最头疼。一个可靠的技巧是把每次恢复现场写成和“进入时的操作”严格对称的顺序。进入时先改状态再递归返回时按相反顺序还原。我自己吃过亏之后现在写DFS都会在函数开头先备份一下关键状态数组快速对比排查。另外推荐一个小工具思维在调试时把path和used打印出来看每次递归进出时变化是否对称。递归不像循环有明确的断点用打印来当“望远镜”看调用栈内容很有效。4.2 汉诺塔步数计算的边界情况汉诺塔第m步这道题最容易出错的边界情况集中在三个地方n1时只有一步即把唯一盘子从源柱移到目标柱。如果m不等于1应该报错或者直接返回空。m等于2^(n-1)时恰好是中间那个大盘子移动的步数此时直接返回对应移动描述。m超出总步数2^n-1的范围时需要提前判断并处理。如果用的是逐步模拟法递归里计数器累加还要注意计数器的初始值。有的同学喜欢把计数器从1开始有的从0开始总会在某个边界差1。我的建议是用累加步数法时判断条件写成“步数加一后与m相等”而不是“当前步数与m相等”思路更顺。如果你用的是数学定位法记得用移位运算时要防止负数位移这就是前面提到的n1特判必须先处理。另外Python里左移和右移对于负数采用的是算术移位容易踩坑写代码时应坚持对n做正向检查。4.3 数字游戏中前缀零与除零陷阱数字游戏里有两个常见的坑一个是前导零一个是除数为零。前导零场景出现在“数字串分段插入运算符”的题目中比如原始字符串是“101”如果你在中间切分出“01”这一段把它当作整数1处理逻辑上非法。标准的处理方式是判断这一段长度大于1且首字符为0直接跳过这个分支。除法场景出现在“数字凑目标值”版本中。由于除法结果可能产生小数很多题目的做法是判断整除后才允许使用除法运算否则就跳过这个分支。实际操作时要注意浮点数比较的精度问题直接判断a / b target可能会因浮点误差出错更稳妥的是在判断二叉运算结果时统一使用分数Fraction类型或者保留除法为小数并设置一个极小的误差容忍比如abs(result - target) 1e-9。下表是我整理的排查清单刷这类递归/DFS题目时可以对照自查问题现象常见原因排查方式输出结果重复未用used数组标记已选数字检查递归返回后是否恢复标记输出结果缺失剪枝条件过强误杀了合法分支临时注释剪枝代码对比输出栈溢出递归层数过大n达数万以上考虑尾递归优化或改非递归步数/计数差1计数器起止值或判断时机错误打印每一步操作与计数器值结果有顺序错误未对初始数据排序或DFS遍历顺序不对对输入数据排序后再DFS除法导致错误浮点数精度或未判断整除使用分数运算或加误差容忍5. 一些过来人的刷题建议这三个题虽然难度不大但属于“看似简单、实则后劲足”的类型。如果你能把每道题背后的原理吃透再往下刷排列组合、N皇后、数独求解、表达式构造这一类DFS题就会轻松很多。这里分享几个我自己的方法。第一不要把递归和DFS割裂开学。刷汉诺塔的时候主动去画递归树把每一步移动对应到树上的一个节点刷全排列的时候也画树你会发现两者的结构几乎一样。理解了这一层后面遇到任何DFS题都能很快想到递归模板。第二尽量做一次“从递归到非递归”的改写练习。拿你刚刷过的任何一道DFS题把递归改成显式栈用自定义状态类存储当前路径和选择状态。这个练习虽然有点反直觉但做完之后你对函数调用栈和“现场保存”的理解会上升到新高度。第三注意输出顺序和格式。编程题的评测机对输出顺序很敏感DFS的遍历方向直接决定结果顺序。全排列类的题目一般要求字典序所以原始数据要先排序汉诺塔类题目要求按指定格式输出移动描述建议写一个统一的格式化函数避免在递归各分支里复制粘贴字符串导致格式不统一。第四重视复杂度估算。三道题的数据范围都不大但如果你养成了“先估算再动手”的习惯后面碰见大数据范围的题目就不慌。全排列复杂度是阶乘级汉诺塔是2的幂级数字游戏枚举所有运算符组合是3^(n-1)级别这些都值得你一眼识别出来。我在刷完这三道题之后最大的感受是递归不是一种“玄学”它只是一种特殊的控制流。当你把它和树、栈、状态恢复这些概念打通之后再碰到的递归题基本都能翻译成DFS模板。反过来DFS的每一层递归也都在实践着汉诺塔里“先处理子问题再处理当前问题再处理另一个子问题”的结构。这个模式一旦形成肌肉记忆一道题接一道题地刷下去会越来越顺畅很少再被“递归好难”这种心理卡住。