1292 字
6 分钟
递归学习笔记
递归(Recursion)的定义
递归是一种解决问题的方法，其精髓在于：
将问题分解为规模更小的相同问题，
持续分解，直到问题规模小到可以用非常简单直接的方式来解决。
递归的问题分解方式非常独特，其算法方面的明显特征就是:在算法流程中调用自身。
例子：数列求和
def listsum(numlist): if len(numlist) = 1: return numlist[0] else: return numlist[0] + listsum(numlist[1:])递归三定律：
- 递归算法必须有一个基本结束条件（最小规模问题的直接解决）
- 递归算法必须能改变状态向基本结束条件演进（减小问题规模）
- 递归算法必须调用自身（解决减小了规模的相同问题）
递归的应用
任意进制转换
def toStr(n,base): convertString = "0123456789ABCDEF" if n < base: return convertString[n] else: return toStr(n//base,base) + convertString[n%base]当一个函数被调用的时候，系统会把调用时的现场数据（栈帧）压入到系统调用栈
当函数返回时，要从调用栈的栈顶取得返回地址，恢复现场，弹出栈帧，按地址返回
河内塔问题
def moveTower(height,fromPole,withPole,toPole): if height >= 1: moveTower(height - 1,fromPole,toPole,withPole) moveDisk(height,fromPole,toPole) moveTower(height - 1,withPole,fromPole,toPole)
def moveDisk(disk,fromPole,toPole): print(f"Moving disk[{disk}] from {fromPole} to {toPole}")
moveTower(3,"#1","#2","#3")探索迷宫 DFS（深度优先搜索）
让海龟探索迷宫
比如：
'#', 'S', '#', '#', '#', '#', '#', '#', '#', '#','#', '*', '*', '#', '#', '#', '#', '#', '#', '#','#', '#', '*', '#', '#', '#', '#', '#', '#', '#','#', '#', '*', '*', '#', '#', '#', '#', '#', '#','#', '#', '#', '*', '#', '#', '#', '#', '#', '#','#', '*', '*', '*', '#', '#', '#', 'E', '#', '#','#', '*', '#', '#', '#', '#', '#', '*', '#', '#','#', '*', '#', '#', '#', '#', '#', '*', '#', '#','#', '*', '*', '*', '*', '*', '*', '*', '#', '#','#', '#', '#', '#', '#', '#', '#', '#', '#', '#'原理：
因此需要加入面包屑机制，沿途撒面包屑，一旦前进发现面包屑，那么就必须换一个方向尝试
对于递归调用来说，就是发现走过的路之后，就从递归调用返回上一级
所以该问题递归调用的基本结束条件如下：
- 碰到墙壁，失败
- 碰到面包屑，失败
- 碰到出口，成功
- 四个方向都无法移动，失败
def dfs_maze(maze, x, y, visited): # 判断越界或遇到墙/面包屑 if x < 0 or x >= len(maze) or y < 0 or y >= len(maze[0]): return False if maze[x][y] == '#' or (x, y) in visited: return False if maze[x][y] == 'E': # 找到出口 print(f"Find end at ({x}, {y})") return True
visited.add((x, y)) # 四个方向: 上下左右 for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]: nx, ny = x+dx, y+dy if dfs_maze(maze, nx, ny, visited): print(f"Step ({x},{y})") return True # 没走通，回溯 return Falseps:话说在ctf里面经常遇到各种迷宫题,当时是使用MazeSolver这个工具做的，现在正好看看其原理
以下是该项目中使用的BFS算法(广度优先搜索)
from collections import deque
def bfs_maze(maze, start_x, start_y): queue = deque() # 队列用于BFS按层推进 visited = set() # 记录已经访问过的位置，避免重复 queue.append((start_x, start_y)) # 加入起点 visited.add((start_x, start_y)) # 标记起点已访问
while queue: x, y = queue.popleft() # 取出当前层要探索的位置 if maze[x][y] == 'E': # 如果当前格子是出口 print(f"Find end at ({x}, {y})") return True # 循环尝试上下左右四个方向 for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]: nx, ny = x + dx, y + dy # 新坐标 # 判断是否越界 if 0 <= nx < len(maze) and 0 <= ny < len(maze[0]): # 不是墙壁且未访问过 if maze[nx][ny] != '#' and (nx, ny) not in visited: queue.append((nx, ny)) # 加入队列等待后续探索 visited.add((nx, ny)) # 标记访问 return False # 队列空了还没找到出口，返回失败使用BFS的情况
- 需要最短路径
- 路径长度是主要考虑因素
- 图比较宽但不太深
使用DFS的情况
- 只需要任意路径（不需要最短）
- 需要回溯搜索（如回溯算法）
- 图比较深但不太宽
- 需要深度优先的特性（如拓扑排序、强连通分量）
总结表格
| 特性 | BFS（广度优先） | DFS（深度优先） |
|---|---|---|
| 数据结构 | 队列（Queue） | 栈（Stack）或递归 |
| 搜索方式 | 逐层搜索 | 深入后回溯 |
| 最短路径 | ✅ 保证 | ❌ 不保证 |
| 时间复杂度 | O(V+E) | O(V+E) |
| 空间复杂度 | O(V) | O(H) 或 O(V) |
| 递归深度限制 | 无（迭代实现） | 可能溢出 |
| 代码复杂度 | 中等 | 简单（递归） |
| 适用场景 | 最短路径问题 | 任意路径、回溯问题 |
V 和 E 的含义：
-
V (Vertices)：顶点数，在图/迷宫中表示节点数
-
在迷宫中：可通行的格子数（不包括墙壁）
-
例如：10×10 迷宫，可通行格子约 50 个，则 V ≈ 50
-
-
E (Edges)：边数，在图/迷宫中表示连接关系数
-
在迷宫中：相邻可通行格子之间的连接数
-
每个格子最多有 4 个方向（上下左右），所以每个格子最多有 4 条边
-
对于 V 个格子，E 通常约为 2V 到 4V（取决于迷宫结构）
-
分治策略
分而治之：
- 将问题分为若干更小的部分
- 通过解决每一个小规模的部分问题，并将结果汇总得到原问题的解
分享
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时