1. 从画正方形到走迷宫递归思维的一次真实跨越很多人学递归卡在同一个地方能看懂阶乘和斐波那契数列的代码但一旦让自己用递归去解决一个稍微带点空间感的问题脑子就转不动了。这不是智力问题而是因为阶乘这类例子的递归结构太线性了——它只沿着一个方向展开没有分支没有回溯没有试错的过程。而真正让递归思维落地的是那些带有分支探索和状态回退的场景迷宫探索就是其中最经典的一个。这篇内容要聊的就是用 Python 配合 turtle 图形库实现一个可视化的迷宫探索程序。核心算法是递归回溯核心看点是你能亲眼看到程序在迷宫里撞墙、回头、换路的全过程。它适合已经了解 Python 基础语法、知道函数怎么定义和调用、但对递归还停留在能看懂但不会写阶段的读者。如果你之前跟着画过螺旋线、分形树之类的 turtle 练习那这篇正好是下一步。我选择 turtle 而不是直接打印字符迷宫原因很实在递归回溯的执行顺序是嵌套的光看控制台输出你很难建立起哪一层在探索、哪一层在回退的空间直觉。turtle 把每一步画出来配合适当的延时递归的进入和返回就变成了肉眼可见的画笔移动。这种直观性是任何文字描述都替代不了的。在正式开始之前先明确一下我们要做的事情边界给定一个用二维列表表示的迷宫起点在左上角终点在右下角用递归的方式找到一条通路并用 turtle 把探索过程动态画出来。不涉及最短路径保证不涉及加权代价就是最纯粹的深度优先搜索加回溯。把这一件事做透递归的空间思维就算真正建立起来了。2. 迷宫的数据结构为什么用二维列表而不是别的2.1 二维列表表示法的取舍逻辑迷宫在程序里怎么存直接决定了后面递归代码的写法。常见的表示方式有三种二维列表、图结构邻接表、以及字符串数组。我这里选二维列表理由是它在可读性和操作便利性之间取得了最好的平衡。具体来说用0表示可以走的通路用1表示墙壁。整个迷宫就是一个嵌套列表比如一个 5x5 的迷宫长这样maze [ [0, 1, 0, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 1, 0], [1, 1, 0, 0, 0], [0, 0, 0, 1, 0] ]访问maze[row][col]就能拿到某个位置的状态判断墙还是路只需要一次比较。如果用图结构你得先建节点、再建边对于这种规则网格来说属于过度设计。字符串数组虽然看起来直观但修改状态标记已访问时不如列表方便因为字符串不可变每次修改都要重建。提示行索引对应 y 方向上下列索引对应 x 方向左右。这个对应关系在画图时非常关键搞反了迷宫就会上下颠倒。2.2 坐标系统与 turtle 屏幕的映射关系turtle 的坐标系原点在屏幕正中央x 轴向右为正y 轴向上为正。而我们的迷宫二维列表maze[0][0]在左上角。这两套坐标系必须做一次转换否则画出来的迷宫是反的。我采用的做法是把迷宫左上角映射到 turtle 屏幕的左上区域每个格子固定边长比如 40 像素。那么对于第row行、第col列的格子它的左上角在 turtle 坐标系里的位置是cell_size 40 origin_x -200 # 迷宫左上角在屏幕上的 x 坐标 origin_y 200 # 迷宫左上角在屏幕上的 y 坐标 x origin_x col * cell_size y origin_y - row * cell_size注意y是减去row * cell_size因为行号越大越往下而 turtle 的 y 轴向上为正所以要用减法。这个细节看起来简单但实际写的时候特别容易搞错我见过不少人在这里卡了半天画出来的迷宫整个是镜像的。2.3 墙壁的绘制一笔画格子还是逐格判断画迷宫墙壁有两种思路。一种是把每个格子都画成方框然后根据是否是墙来填充颜色另一种是只画墙格子的填充矩形。我推荐后者因为视觉上更干净而且绘制代码更少。对于每个值为1的格子用 turtle 的begin_fill()和end_fill()画一个填充矩形。这里有个性能上的小细节如果迷宫比较大比如 20x20 以上每画一个格子都抬笔落笔会明显变慢。我的做法是先tracer(0)关闭自动刷新画完整个迷宫后再update()一次性刷新。这样即使 50x50 的迷宫也是瞬间画完。def draw_cell(t, x, y, size, color): t.penup() t.goto(x, y) t.pendown() t.fillcolor(color) t.begin_fill() for _ in range(4): t.forward(size) t.right(90) t.end_fill()这段代码里t.right(90)执行四次正好转一圈是画正方形最简洁的写法。注意 turtle 默认朝向是向右东所以从左上角开始画先向右、再向下、再向左、再向上刚好闭合。3. 递归回溯的核心把试错翻译成函数调用3.1 递归函数的四个关键判断迷宫探索的递归函数本质上是在回答一个问题从当前位置出发能不能走到终点这个问题的递归结构体现在如果当前位置的四个邻居中有一个能走到终点那么当前位置就能走到终点。一个完整的递归函数需要处理四种情况我按优先级排列越界判断当前位置超出了迷宫范围直接返回 False。墙壁判断当前位置是墙值为 1返回 False。已访问判断当前位置之前已经走过返回 False避免死循环。终点判断当前位置就是终点返回 True。只有这四种情况都不满足才进入真正的探索逻辑标记当前位置为已访问然后依次尝试四个方向只要有一个方向返回 True就说明找到了通路当前层也返回 True。如果四个方向都失败说明当前位置是死胡同返回 False让上一层去尝试别的方向。def solve_maze(maze, row, col, end_row, end_col, visited): # 越界 if row 0 or row len(maze) or col 0 or col len(maze[0]): return False # 墙壁 if maze[row][col] 1: return False # 已访问 if (row, col) in visited: return False # 终点 if row end_row and col end_col: visited.add((row, col)) return True visited.add((row, col)) # 依次尝试四个方向下、右、上、左 for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]: if solve_maze(maze, row dr, col dc, end_row, end_col, visited): return True return False3.2 为什么 visited 用集合而不是修改原迷宫标记已访问有两种常见做法一是把maze[row][col]改成2之类的标记值二是用一个独立的visited集合。我强烈推荐后者原因有两个。第一修改原迷宫会破坏数据。如果后面你还想重新探索或者展示原始迷宫原数据已经被污染了。第二用集合的查找是 O(1) 的和修改列表元素的效率一样但语义更清晰——访问过的位置和迷宫本身的结构是两回事不应该混在一起。注意如果你确实想用修改原迷宫的方式记得在回溯时把值改回去否则会影响其他路径的探索。但这样一来代码就复杂了不如直接用集合省心。3.3 递归的进入与返回到底发生了什么这是理解递归最关键的一环。当solve_maze调用自身去探索下方邻居时当前这一层的执行是暂停的程序的控制权交给了新的一层。新的一层如果找到了通路会返回 True这个 True 会一层层往上传每一层都直接return True不再尝试其他方向。如果新的一层返回 False说明那个方向走不通当前层就继续 for 循环的下一个方向。这就是回溯的本质——不是真的退回去而是当前层的循环继续执行。我用一个具体的例子来说明。假设起点是 (0,0)它先尝试向下走到 (1,0)。如果 (1,0) 是个死胡同那么 (1,0) 这一层的四个方向都返回 False它自己返回 False。控制权回到 (0,0) 这一层(0,0) 的 for 循环继续尝试下一个方向 (0,1)。整个过程就像你在迷宫里走走进一条死路后原路返回到上一个岔路口换一条路继续走。4. 让递归过程看得见turtle 动画的节奏控制4.1 画笔移动与递归调用的同步光有算法还不够我们要让 turtle 的画笔跟着递归的脚步走。核心思路是在递归函数进入某一格时让画笔移动到该格中心并画一个标记在递归返回 False 时把标记改成另一种颜色表示此路不通。这里有个顺序问题需要特别注意。画笔的移动应该发生在判断这一格是否可走之后而不是之前。否则你会看到画笔跑到墙里面去画标记视觉上很混乱。我的做法是在确认当前格可走之后先画一个正在探索的标记然后再进入四个方向的递归。def draw_marker(t, row, col, color, size40): x origin_x col * size size // 2 y origin_y - row * size - size // 2 t.penup() t.goto(x, y) t.pendown() t.dot(size // 2, color)用t.dot()画圆点比画正方形更简洁而且圆点不会遮挡迷宫的墙壁线条。颜色上我用蓝色表示正在探索的路径用灰色表示已经确认走不通的死路用绿色表示最终找到的通路。4.2 延时与刷新找到可观察和可忍受的平衡点如果递归执行得太快你什么都看不清如果太慢一个 10x10 的迷宫可能要跑好几分钟。我的经验值是每步延时 0.05 到 0.1 秒这个区间既能看清画笔的移动轨迹又不至于让人等得不耐烦。实现延时用time.sleep()就行但要注意 turtle 的屏幕刷新机制。如果你用了tracer(0)来加速初始绘制那么在动画阶段需要恢复tracer(1)否则time.sleep()期间屏幕不会更新你看到的还是一片空白。import time # 动画阶段 screen.tracer(1) time.sleep(0.08)另一个技巧是对于死路回退的标记可以比前进的标记延时更短比如 0.03 秒。因为回退是批量发生的如果每个回退都等 0.1 秒视觉上会显得拖沓。4.3 最终路径的高亮回溯结果的二次绘制递归函数返回 True 之后我们只知道存在通路但不知道具体是哪条路。要画出最终路径有两个办法。第一个办法是在递归返回 True 的时候把当前格加入一个路径列表。因为 True 是一层层往上传的每一层都会执行到这个加入操作所以最终列表里就是完整的通路。这个办法最简洁path [] def solve_maze(maze, row, col, end_row, end_col, visited): # ... 前面的判断 ... if row end_row and col end_col: visited.add((row, col)) path.append((row, col)) return True visited.add((row, col)) for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]: if solve_maze(maze, row dr, col dc, end_row, end_col, visited): path.append((row, col)) return True return False注意path.append的位置在return True之前这样每一层成功返回时都会把自己的坐标加进去。最终path里就是从终点到起点的完整路径顺序是反的画的时候倒过来就行。第二个办法是递归结束后根据visited集合和迷宫结构重新做一次搜索。这个办法代码更多而且容易出错不推荐。拿到路径后用绿色圆点重新覆盖一遍通路就一目了然了。如果想让效果更明显可以把路径上的圆点画得比探索标记稍大一点。5. 实测中遇到的三个坑和对应的解法5.1 递归深度超限小迷宫没事大迷宫崩溃Python 默认的递归深度限制是 1000 层。对于 10x10 的迷宫最坏情况下递归深度可能达到 100 层左右没问题。但如果你把迷宫扩大到 50x50最坏情况下的递归深度可能超过 1000程序会抛出RecursionError。解决办法有两个。一是用sys.setrecursionlimit()提高限制import sys sys.setrecursionlimit(10000)二是改用迭代加显式栈的方式重写。但既然这篇的主题是递归我建议先用第一种办法。不过要提醒一句提高递归限制并不是越高越好设得太高可能导致真正的栈溢出把限制设在 5000 到 10000 之间比较稳妥。提示如果你发现迷宫稍微大一点就崩溃先检查是不是迷宫里有大量死胡同导致递归深度激增。有时候换一个迷宫生成算法比如用深度优先生成的迷宫通路更蜿蜒递归深度反而更可控。5.2 方向顺序影响探索路径为什么下右上左而不是上下左右四个方向的尝试顺序会直接影响最终找到的路径长什么样。我用的顺序是下、右、上、左。这个顺序不是随便定的。在起点左上角、终点右下角的迷宫布局下优先向下和向右会让探索路径更倾向于朝着终点的大方向前进视觉上更合理。如果先尝试向上和向左画笔会频繁地往回走看起来像是在绕远路虽然最终也能找到通路但观感差很多。当然这个顺序不是绝对的。如果你的起点和终点位置不同可以相应调整。核心原则是优先尝试朝向终点方向的那两个方向。这样探索过程更符合人的直觉也更容易理解。5.3 已访问标记的时机早标记还是晚标记标记已访问的时机有一个非常隐蔽的坑。如果你在进入函数的第一时间就标记那么当这一格最终被证明是死路时它仍然留在visited集合里。这本身没问题因为死路确实不需要再走。但如果你在标记之前就判断终点而终点恰好被标记过就会出问题。我的做法是终点判断放在已访问判断之后但在标记之前。也就是说先检查是不是终点如果是标记并返回 True如果不是再标记并继续探索。这样保证终点一定会被标记而且不会被已访问逻辑挡住。另一个细节是visited.add()应该放在递归调用之前而不是之后。如果放在之后同一格可能在一次递归中被多次加入虽然集合会自动去重但逻辑上不清晰。6. 从迷宫探索延伸出去的递归思维把迷宫探索跑通之后你会发现递归回溯这个模式可以套用到很多问题上。数独求解本质上就是迷宫探索的变体——每个空格尝试填入 1 到 9如果导致矛盾就回退换一个数字。八皇后问题也是一样每一行尝试放置皇后如果和之前的皇后冲突就换列。这些问题的共同结构是在每一步有多个选择选择之后需要验证验证失败就撤销选择并尝试下一个。迷宫探索把这个结构最直观地展现了出来因为它的选择是空间上的移动验证是是否撞墙撤销是画笔回退。我在实际教学中发现学员一旦真正理解了迷宫探索的递归流程再去看数独求解的代码理解速度会快很多。因为大脑里已经有了一个可视化的参照物——那个在迷宫里撞墙回头的画笔。如果你想进一步巩固可以尝试这几个改造把迷宫改成带权重的每格有不同代价找一条代价最小的路径或者把递归改成迭代加栈对比两种写法的差异再或者把迷宫生成也做成递归的用深度优先算法随机生成迷宫。每一个改造都会让你对递归的理解更深一层。最后分享一个我在调试递归代码时常用的技巧在递归函数的入口和出口各加一行打印输出当前深度和坐标。虽然控制台输出不如 turtle 直观但在排查逻辑错误时打印日志比看动画更精确。两者结合使用效果最好。