递归与DFS深度解析：核心模板、状态管理及常见题型

这个系列写到第25期，递归却是我一直没敢轻易动的题目。原因很简单：递归这东西看示例都觉得挺好懂，自己一到代码面前就容易卡壳；而DFS——深度优先搜索——又是递归里最典型的那个应用。带过一些刚开始接触算法的人之后，我发现大家卡住的点惊人地一致：不知道dfs函数里该传什么参数，不知道该在哪个时候标记状态，更不知道一个代码明明写完了为什么会输出一堆奇怪的结果。这篇文章我想把这几年来在递归和DFS上积累的经验梳理一遍，不绕弯子，直接把主干骨架、状态管理和最常见的题型拆开讲，让想学会DFS的人少走几步弯路。

1. 从递归到DFS：先搞懂两者到底什么关系

1.1 递归的本质：函数调用自己

很多人把递归当成一种高级技巧，其实它只是“函数自己调用自己”这件事而已。为什么需要自己调用自己？因为你要解决的问题，可以被拆成一个更小的同类问题。比如算n!，你只需要知道(n-1)!，乘一个n就结束了；遍历一个文件夹，你只需要遍历里面每一个子文件夹，而子文件夹的结构和当前文件夹完全一样。递归就是在这种“结构自相似”的场景下，让同一个函数反复处理规模更小的输入。

写递归有一个铁三角：终止条件、递推公式、边界处理。终止条件（也叫 base case）是递归最先要写的，因为没有它，函数会无限往深处跑，直到栈爆掉；递推公式说明当前层和下一层之间的关系；边界处理则保证参数在进入下一层之前不会越界。三者缺一不可，但大多数初学者最常忘的就是第一项。

1.2 DFS的本质：一种遍历顺序

深度优先搜索（DFS）听起来像是图论专属名词，实际上它描述的是“怎么走完所有可达节点”的一种顺序：从一个起点出发，沿着一条路一直走到头，走不动了再退回来，换下一条路继续走。这个过程像极了一个人走迷宫：贴着当前岔路的一侧走到底，撞墙了退到上一个岔路口，再换另一侧，直到把整片迷宫都摸遍。

DFS 和递归之所以经常被放在一起说，是因为 DFS 天生适合用递归实现。你可以把递归的调用栈想象成一根往地下打的桩：调用一次dfs就往深走一层，返回值的时候再回到上一层。这和 DFS 的“深入、回溯、再探索”节奏完全对得上。栈帮我们自动记住了“来时的路”，这就是递归写 DFS 不需要手动维护路径的原因。

1.3 为什么学DFS先要练递归

我在实际教别人时发现一个经验：如果你的递归写得还不熟练，直接上手 DFS 会觉得很抽象；但如果递归基本功扎实，DFS 就只是“递归在搜索问题上的一个应用”而已。搜索问题的本质是“在所有可能路径里找到目标路径”，而递归恰好擅长描述路径：每一层递归代表路径上的一步，递归深度就是走了多远。

所以我的建议是，先不急着刷 DFS 题，先把递归最简单的例子练熟：写出一个函数递归打印1到n，再写一个递归求斐波那契数列，甚至用递归去遍历一个嵌套字典。等你能闭眼写出递归模板时，再去看 DFS 的题目，会发现它们只是在问同一件事：“你当前的状态是什么，有哪些选择，边界在哪。”状态代表你已经走到的地方，选择代表下一步可以往哪儿走，边界代表哪些路径可以直接放弃。

2. DFS递归写法的主干与状态管理

2.1 一个几乎能覆盖八成题目的模板

我总结过一个自认为相当通用的 DFS 模板，很多题目只要往里面套就能跑通。模板不长，核心思想是“一条路走到底，走不通就还原现场”：

def dfs(step, state): # 1. 当前状态不合法，直接剪枝返回 if not is_valid(state): return # 2. 到达目标状态，记录答案并返回 if is_target(step, state): record_answer(state) return # 3. 枚举下一步所有可能的选择 for choice in candidate_choices(step, state): state.add(choice) # 做选择 mark_used(choice) # 标记这个选择已被占用 dfs(step + 1, state) # 往下一层走 unmark_used(choice) # 撤销标记 state.remove(choice) # 撤销选择，恢复现场

这个模板看着简单，但里面每一行都有它的作用。is_valid负责处理“这条路径已经不符合条件”的情况，提前返回可以避免无意义的深层遍历；is_target判断是否得到一个完整结果；而for循环是核心，它决定了 DFS 怎么“岔开路”：每个候选选择就是一条新的分支，当前节点先选一条分支走完，再回到这里选下一条分支。

2.2 状态标记与撤销：为什么必须“还原现场”

模板里最容易被人忽略的是「撤销选择」那两行：unmark_used和state.remove。很多初学者会疑惑，我已经把结果存下来了，为什么还要把标记擦掉？这就要回到 DFS 的工作方式了。

在多数搜索问题中，递归函数操作的状态是共享的，也就是所有分支都使用同一份路径列表和同一个标记数组。假设你在第一层选了数字3并标记used[3] = True，到第二层选了数字1，这时得到了一条完整路径[3, 1]。如果不把used[3]恢复成False、不把3从路径里弹出去，等回到第一层准备换选数字1时，你会惊讶地发现used[3]仍然是True，路径还带着残留的3，后续所有分支全乱套了。这就像大家共用一张草稿纸，你画完自己的题不擦掉，下一个人只能在你的笔迹上继续算，结果当然不对。

从递归栈的角度理解更直观：每一层递归的“局部变量”保存在各自的栈帧里，但路径列表和标记数组如果放在全局或作为参数传引用，它们就是所有层共享的。DFS 回溯的过程，本质上是把共享状态从当前分支的状态恢复成分支前的状态，这样才能保证下一个分支从同一个起点出发。

2.3 参数传下去，标记带回来：传参的取舍

写 DFS 时还有一个细节经常决定成败：状态到底是放在参数里，还是放在全局变量里？我的经验是，需要回溯修改的状态，用全局列表或作为可变参数传递；不需要回溯的只读信息，直接传参数即可。

比如路径path这种“边走边加、回溯时删除”的东西，适合作为可变列表传递，或者放在全局变量里统一维护。而像“层数step”这种一旦进入下一层就固定、无需还原的数据，就应该作为普通参数传递。还有一种情况是每个分支都需要一份完全独立的副本，比如一份配置字典，此时需要在进入下一层前复制一份（copy.deepcopy），但这会带来额外开销，所以我会先问自己：这个状态真的需要独立副本吗？还是说通过“标记 + 撤销”就能满足需求？绝大多数题目用“标记 + 撤销”就够，不需要深拷贝。

3. 四个经典题型：没那么神秘

3.1 全排列：进坑、出坑、换下一个

全排列是 DSF 入门的必修课，也是理解回溯机制最好的题目。假设你有n个互不相同的数字，要列出所有长度为n的排列。你可以想象成有n个坑，每个坑要填一个数字，每个数字只能填一次：

def permute(nums): res = [] used = [False] * len(nums) def dfs(path): if len(path) == len(nums): res.append(path[:]) # 取的是副本 return for i in range(len(nums)): if used[i]: continue used[i] = True path.append(nums[i]) dfs(path) path.pop() used[i] = False dfs([]) return res

注意res.append(path[:])这一行：如果不写[:]，把path直接放进去，由于path后续还会被修改，结果列表里的所有“答案”最终会变成同一个空列表或同一个最终列表，这就是初学者最容易遇到的“答案全是空”或“答案全一样”的诡异现象。全排列的时间复杂度是O(n!)，因为每层的分支数分别是n, n-1, n-2, ...，乘在一起就是阶乘级，这个复杂度决定了它只适合小规模输入。

3.2 子集：选或不选的指数分支

与全排列不同，子集问题不需要选完所有元素，它只问你“每个元素，选还是不选”。这种“选或不选”的模型是 DFS 的另一大类，递归树展开后每个节点有两个分支，总共会产生2^n个结果，这就是指数级复杂度的直观来源。

有两种常见写法。第一种是按位置枚举：从第i个元素开始决定要不要把它加入当前集合。第二种是按起点枚举组合，适合生成定长子集。这里给出第一种：

def subsets(nums): res = [] def dfs(idx, path): res.append(path[:]) # 每个节点都是一个子集 for i in range(idx, len(nums)): path.append(nums[i]) dfs(i + 1, path) path.pop() dfs(0, []) return res

这段代码的精妙之处在于：每次进入dfs都先把当前路径记下来，所以它天然就收集了所有前缀组合。dfs(i + 1, ...)保证下一层只从当前元素之后开始选，这样既不会重复选择同一个元素，也不会产生[1,2]和[2,1]这种同集不同序的重复答案。很多人在子集问题上纠结要不要used数组，这里其实不需要，因为i + 1本身就规定了“不能回头看”，这种用下标限制候选集的做法比开标记数组更干净。

3.3 树的遍历：DFS最简单的练功房

如果说全排列和子集是“一层一个坑”的模型，树的遍历则是最直观的 DFS 应用：每个节点有几个子树，就有几条分支。二叉树的先序、中序、后序遍历，本质上都是 DFS 的不同访问时机。先序是“先访问根，再左后右”；中序是“先左，再根，再右”；后序是“先左右，再根”。

用递归写先序遍历，几乎不需要思考：

def preorder(root): if root is None: return [] return [root.val] + preorder(root.left) + preorder(root.right)

不喜欢用加法拼接列表的话，可以把结果列表当作参数传下去：

def preorder(root, res): if root is None: return res.append(root.val) preorder(root.left, res) preorder(root.right, res)

树的题目能帮你建立直觉：DFS 的“路径”在这里就是“当前子树到根节点的访问序列”，递归深度等于树的高度。写完树的遍历再回头看全排列，你会发现它们其实是同一个模板在不同数据结构上的表现：坑是树的节点，选择是下一步走向哪棵子树。

3.4 岛屿数量：把网格当图

网格类 DFS 是面试里出现频率很高的题型，它把二维数组看成一个图，每个格子只有上下左右四条边和邻居相连。经典的“岛屿数量”问题就是：给你一个由1（陆地）和0（水）组成的二维网格，问有几块彼此不连通的陆地。

我的做法是：每遇到一个1，就先把它改成0，然后递归地把相邻所有的1都改成0，这样一个岛屿就被“淹没”了。计算你改了几次，就是岛的数量。核心代码如下：

def num_islands(grid): if not grid: return 0 m, n = len(grid), len(grid[0]) count = 0 def dfs(r, c): if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != '1': return grid[r][c] = '0' # 淹没当前陆地 dfs(r - 1, c) dfs(r + 1, c) dfs(r, c - 1) dfs(r, c + 1) for i in range(m): for j in range(n): if grid[i][j] == '1': count += 1 dfs(i, j) return count

这段代码里最关键的操作是立刻把当前位置改成0。如果不改，递归调用时会反复经过同一个格子，直接死循环。网格 DFS 的边界检查通常放在递归函数的开头，四个方向统一写在最后，这样代码最简洁，也不容易漏方向。我见过有人把边界条件写在for循环里，当然也行，但每次都判断四次边界会显得啰嗦，放递归开头更像“先把状态判死，再放心往下走”的 DFS 哲学。

4. 从能跑到跑过：复杂度、剪枝与记忆化

4.1 先看递归树，再谈复杂度

很多初学者以为写 DFS 只要答案对就行，结果一跑大数据就超时。DFS 的复杂度估算有个很实用的办法：画出递归树，数一下递归调用一共产生了多少个节点，再乘以每个节点上消耗的时间，就是总复杂度。

比如全排列，第一层有n个节点，第二层每个节点又分出n-1个，整棵递归树的节点总数约等于n!级别，每个节点要遍历一次候选数组，所以复杂度是O(n * n!)，通常写作指数/阶乘级。子集问题是2^n个结果，每个结果平均长度O(n)，所以是O(n * 2^n)。网格题则每次递归访问一个格子，每个格子最多被访问一次，因此是O(m * n)，这类题往往不需要担心超时。

4.2 剪枝的本质：把明显不合理的分支提前掐掉

现实中的搜索空间往往比答案空间大得多，如果每个分支都走到底，整数一大的题目根本跑不动。剪枝就是一种“预判”：在进入某个分支之前，就判断这条路不可能得出答案，于是直接跳过。

剪枝最常见的形式有几种：一是“可行性剪枝”，比如在组合题里，当前路径长度加上剩余可选元素已经凑不齐目标长度，就没必要继续递归；二是“重复性剪枝”，比如排列题里如果数字有重复，可以事先排序，跳过和前一个相同的数字；三是“提前终止”，比如只需要找一条路径，在找到答案后直接抛出异常或返回True，不再往下搜索。

判断什么时候能剪枝需要具体问题具体分析，但有一个通用思路：先写出不加剪枝的暴力 DFS，然后看哪一层分支数量特别大，针对这一层最费时的分支想一个“必须满足的前提条件”。这个前提条件就是剪枝条件。我试过不少题目，单纯加一句if就能把耗时从几十秒降到毫秒级。

4.3 DFS + 缓存：自顶向下的记忆化搜索

有一类问题，DFS 在递归过程中会反复计算同一个状态。最典型的例子是斐波那契数列：fib(5)会递归调用fib(4)和fib(3)，而fib(4)又会调用fib(3)和fib(2)，fib(3)被重复计算了两次。这种重复计算会让原本线性的问题膨胀成2^n的复杂度。

解决办法是加一个缓存字典（记忆化），每次进入dfs时先查表，算完再写表：

def fib(n, memo=None): if memo is None: 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]

记忆化搜索的意义在于：它把 DFS 从“探索所有路径”变成了“只计算每个状态一次”，本质就是自顶向下的动态规划。很多人觉得动态规划难，其实可以先从 DFS 入手：先用递归写一个朴素版，发现超时后加memo，最后再看看能不能改成数组递推。这条路径是我强烈推荐的 DP 学习路线。判断一个题目适不适合记忆化，关键是看“当前状态是否被多条路径共享”——如果每次状态计算只被一条路径经过，缓存就没什么用。

5. 递归的坑：调试DFS的正确姿势

5.1 最常见的四个错误

写 DFS 最容易踩的坑，我总结成四类，几乎涵盖了九成以上的报错现场：

第一类是忘记终止条件。递归函数没有if出口，或者出口条件永远不满足，Python 会直接报RecursionError: maximum recursion depth exceeded。解决办法是写函数之前先把终止条件列出来，放在函数第一行，优先级最高。

第二类是状态没有恢复。used标记了不撤销，路径添加了不弹出，导致下一分支看到的是上一分支的残留状态。典型症状是答案数量偏少、路径缺元素或者重复得很怪。

第三类是答案列表存了引用。前面提到的path[:]问题，直接把可变对象append进结果列表，后面一修改，所有历史结果跟着变。

第四类是默认参数踩雷。如果写成def dfs(visited=set())，这个visited会在所有递归调用之间共享，甚至在下一次调用整个dfs函数时还保留上一次的数据。我每次见到有人问“为什么第二次调用结果不对”，八成就是这个原因。可变默认参数一律改成None，在函数内部再初始化为空集合或空字典。

下表把这四类问题归纳出来方便自查：

5.2 实战调试方法：打印缩进、小用例手推

调试 DFS 不像调试普通顺序代码，大脑很难同时想象出整棵递归树的走向。我常用的一个笨但有效的办法是：在递归函数开头打印当前路径，并按照递归深度缩进，让递归树的形状直接“可视化”出来：

def dfs(path, depth=0): print(" " * depth + "当前路径:", path) ...

这样运行时你能看到每一步是从哪一层进入的。如果某个分支的路径突然多了一个不该有的元素，那一定是在进入这个分支之前有状态没清理干净，顺着打印结果往回看，很快就能定位到哪一层少写了pop或unmark。

还有一种方法是拿极小用例手推。比如全排列就用nums = [1, 2]，把整棵递归树在纸上走一遍：先选1，再选2，得到[1, 2]；回溯；然后选2，再选1。每一步对照代码里的for循环、append、pop，走完一遍，代码里哪里多写或少写一目了然。

5.3 栈溢出怎么救

Python 默认递归深度限制通常是 1000 层，这在大多数面试题里够用，但一旦遇到链式树（比如一条线型的图），深度就可能上万。直接调用sys.setrecursionlimit(1000000)可以把限制调高，但这只是让 Python 允许你继续递归，不代表内存扛得住。每一层递归都要占用调用栈空间，深度过深照样会把进程压垮。

我的建议是藕：先判断最大递归深度到底有多大。如果题目给的规模在几千层以内，调一下setrecursionlimit还能应付；如果深度的数量级在十万、百万级，就应该考虑第二种方案——用显式栈把递归改成迭代。下一章会专门讲怎么改。切记，setrecursionlimit是“解除限制”，不是“扩大内存”，它不能解决所有栈溢出问题。

6. 当递归不够用：把DFS改写成迭代栈

6.1 为什么需要迭代写法

虽然递归写 DFS 最自然，但有几种情况你必须考虑迭代写法：一是递归深度超过 Python 的安全范围，报RecursionError；二是有些在线评测环境或嵌入式环境不允许使用递归；三是为了彻底理解 DFS 的内部过程，手动模拟栈能帮你把“系统栈隐式做的事”变成“显式维护的数据结构”。

迭代写法的核心思路是：不再依赖调用栈保存路径，而是自己维护一个栈来存储“接下来要访问的节点”。这其实就是把递归时系统帮我们做的事，搬到代码里自己来做。

6.2 一个通用模板：用栈模拟递归调用

先看最简单的树先序遍历迭代版：

def preorder_iter(root): if root is None: return [] res = [] stack = [root] while stack: node = stack.pop() res.append(node.val) # 栈是后进先出，想先访问左子树，就要先把右子树压入栈 if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res

这个版本只适合先序遍历。但对于更通用的回溯场景，我推荐一个可以同时模拟“进入递归”“处理结果”“返回上一层”三段逻辑的框架：栈里放(node, visited_flag)，visited_flag表示这个节点是否已经处理过其子节点。

def dfs_iter(root): stack = [(root, False)] while stack: node, visited = stack.pop() if node is None: continue if visited: # 已经处理完子节点，回到这里做“后处理” res.append(node.val) else: # 先压入后处理标记，再压入子节点 stack.append((node, True)) stack.append((node.right, False)) stack.append((node.left, False)) return res

这个(node, visited)的技巧可以统一模拟先序、中序、后序遍历，只要调整压栈顺序和“处理节点”的位置就能切换。如果你想更彻底地模拟递归的每一层，还可以在栈里存“当前层还需要做什么”，这种做法虽然繁琐，但在某些复杂回溯题里很实用。

6.3 网格搜索时的迭代写法

网格题也可以改迭代版，而且改起来更直观。以岛屿数量为例，递归版的核心是“进入一个1，立刻改成0防止重复访问”；迭代版只需要把这个动作换成“弹出格子时改，同时把相邻陆地压入栈”：

def num_islands_iter(grid): if not grid: return 0 m, n = len(grid), len(grid[0]) count = 0 for i in range(m): for j in range(n): if grid[i][j] == '1': count += 1 grid[i][j] = '0' stack = [(i, j)] while stack: r, c = stack.pop() for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)): if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '1': grid[nr][nc] = '0' stack.append((nr, nc)) return count

这个迭代版和前面的递归版，结构几乎是一一对应的：递归函数的入口dfs(i, j)对应循环里stack.append初始坐标；递归里对四个邻居调用dfs对应迭代里把邻居压栈；递归里“进入函数立刻改0”对应迭代里“压栈前立刻改0”。理解了这种对应关系，以后任何 DFS 题目都能在递归和迭代之间自由切换。

我自己在实际操作中的习惯是：先用递归把思路写通，确认答案正确；如果题目规模暗示递归深度可能超限，再照着这个(状态, 已处理标记)的模板改成迭代。改的过程中一旦出现遍历顺序或输出结果不一致，就把两种版本在同一个最小用例上跑，对比每一步弹出的节点和路径，通常很快就能找到差异在哪。写 DFS 这件事，本质上就是一个不断“入栈—出栈—还原—再入栈”的循环，递归只是把栈藏在了系统背后。只要把这个栈从幕后拿到台前，你就不只是会写 DFS，而是真正掌握了它。