递归与搜索
掌握了DFS/BFS，就拿下了省赛的半壁江山。
前几篇我们复习了IO、数据结构、标准库，今天进入算法核心——递归与搜索。省赛搜索类题目占比极高，从填空题的暴力枚举到大题的迷宫、路径、状态搜索，几乎每场都有2-3道题涉及。选Python的优势在于：写搜索非常直观，配合标准库可以快速实现。
递归
自己调用自己
1. 递归三要素
defrecursion(参数):
# 1. 终止
if 终止条件:
return 基础值
# 2. 处理当前层
# 3. 递归调用（缩小问题规模）
return recursion(缩小后的参数)
2. 经典例子：斐波那契
deffib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
这个写法虽然简洁，但存在大量重复计算。优化方案：记忆化
3. 递归的坑
- 递归深度限制：Python默认递归深度1000，必须设置
sys.setrecursionlimit(1000000) - 栈溢出：递归太深可能导致栈溢出，考虑用迭代或BFS
- 全局变量：在递归函数内修改全局变量前要声明
global
import sys
sys.setrecursionlimit(1000000) # 要放在程序开头
DFS
深度优先搜索：一条路走到黑
DFS的核心思想：从起点出发，沿着一个方向一直探索，直到无法继续，然后回溯到上一个节点，换方向继续。
1. 基础模板
defdfs(状态参数):
# 终止条件：找到答案或无法继续
if 满足条件:
记录结果
return
# 遍历所有可能的选择
for 选择 in 可选列表:
if 选择合法:
做出选择（标记已访问）
dfs(新状态)
撤销选择（回溯）
2. 全排列
经典回溯
defpermute(nums):
res = []
n = len(nums)
used = [False] * n
defdfs(path):
if len(path) == n:
res.append(path[:]) # 注意拷贝
return
for i in range(n):
ifnot used[i]:
used[i] = True
path.append(nums[i])
dfs(path)
path.pop()
used[i] = False
dfs([])
return res
3. 迷宫DFS（二维网格）
directions = [(1,0), (-1,0), (0,1), (0,-1)]
defdfs(x, y):
# 越界或撞墙
if x < 0or x >= m or y < 0or y >= n or maze[x][y] == '#':
return
# 到达终点
if (x, y) == target:
returnTrue
# 标记已访问
maze[x][y] = '#'
for dx, dy in directions:
if dfs(x+dx, y+dy):
returnTrue
returnFalse
4. 剪枝技巧
剪枝就是提前终止无效搜索，可以大幅提升效率。
defdfs(参数):
# 可行性剪枝：当前状态已经不可能得到解
if 当前不可能:
return
# 最优性剪枝：当前解已经不如已找到的最优解
if 当前代价 >= best:
return
# 顺序剪枝：优先搜索可能性大的分支
for 选择 in 排序后的可选列表:
# ...
BFS
广度优先搜索：层层推进
BFS的核心思想：从起点开始，一层一层向外扩展，第一次到达终点时一定是最短路径。
1. 基础模板（队列实现）
from collections import deque
defbfs(start, target):
queue = deque([start])
visited = set([start])
distance = {start: 0}
while queue:
cur = queue.popleft()
if cur == target:
return distance[cur]
for next_state in get_neighbors(cur):
if next_state notin visited:
visited.add(next_state)
distance[next_state] = distance[cur] + 1
queue.append(next_state)
return-1# 不可达
2. 迷宫最短路径
from collections import deque
defbfs_shortest_path(maze, start, end):
m, n = len(maze), len(maze[0])
directions = [(1,0), (-1,0), (0,1), (0,-1)]
queue = deque([(start[0], start[1], 0)]) # (x, y, dist)
visited = [[False]*n for _ in range(m)]
visited[start[0]][start[1]] = True
while queue:
x, y, dist = queue.popleft()
if (x, y) == end:
return dist
for dx, dy in directions:
nx, ny = x+dx, y+dy
if0 <= nx < m and0 <= ny < n andnot visited[nx][ny] and maze[nx][ny] != '#':
visited[nx][ny] = True
queue.append((nx, ny, dist+1))
return-1
3. BFS vs DFS 选择
记忆化搜索：DFS + 缓存
记忆化搜索是DFS的优化版，通过缓存已计算的状态，避免重复递归。本质是自顶向下的动态规划
1. 使用 lru_cache
from functools import lru_cache
@lru_cache(maxsize=None)
defdfs(i, j):
if i == 0and j == 0:
return1
if i < 0or j < 0:
return0
return dfs(i-1, j) + dfs(i, j-1)
上面的代码计算从 (0,0) 到 (m,n) 的路径数，自动缓存中间结果。
2. 手写记忆化数组
memo = [[-1]*n for _ in range(m)]
defdfs(x, y):
if memo[x][y] != -1:
return memo[x][y]
# 递归计算
memo[x][y] = 结果
return memo[x][y]
3. 典型应用：数字三角形、滑雪问题、博弈问题
常见搜索题型
1. 迷宫类（DFS/BFS）
2. 排列组合类（DFS+回溯）
3. 状态压缩搜索（BFS）
4. 记忆化搜索（DFS+DP）
常见错误与调试技巧
1. 忘记标记已访问（死循环）
# 错误
defdfs(x, y):
for dx, dy in dirs:
dfs(x+dx, y+dy)
# 正确
visited[x][y] = True
for dx, dy in dirs:
ifnot visited[x+dx][y+dy]:
dfs(x+dx, y+dy)
# 回溯时是否要撤销标记取决于场景
2. 在BFS中忘记分层
需要知道当前距离时，最好在队列中存距离，或分层处理
queue.append((x, y, dist))
3. 递归深度过大
4. 回溯时忘记恢复状态
path.append(x)
dfs()
path.pop() # 必须恢复
5. 列表作为参数传递时，是引用
错误res.append(path)
后面path变化会影响已保存的结果 正确res.append(path[:])
拷贝一份
小结
