如何将查找矩阵从左上到右下全路径的递归函数转换为迭代函数?
递归转迭代的实现方案
递归转迭代的核心是手动模拟系统调用栈的状态,处理好递归的后序回溯操作(也就是原函数里path.pop()的逻辑),这里可以用带访问标记的栈实现,完全对齐原递归的执行逻辑,输出顺序和原代码完全一致。
实现原理
原递归的执行流程分为三步:
- 将当前节点加入路径,判断是否到达终点,到达则输出路径
- 按顺序尝试三个合法移动方向,递归处理每个方向的子节点
- 所有子节点处理完成后,将当前节点从路径中弹出(回溯)
迭代实现时,因为栈是后进先出结构,需要给栈中元素增加是否已处理子节点的标记:
- 第一次弹出未处理的节点:执行「加入路径」的操作,再把带「已处理」标记的当前节点压回栈中,最后把所有合法的子节点按与原递归相反的顺序压栈(保证弹出顺序和原递归一致)
- 弹出已处理的节点:执行「弹出路径末尾元素」的回溯操作
DFS迭代版(贴合原逻辑,空间复杂度低)
def findPathsIter(mat): M, N = len(mat), len(mat[0]) # 栈元素格式: (当前行i, 当前列j, 是否已处理子节点) stack = [(0, 0, False)] path = [] while stack: i, j, is_processed = stack.pop() if not is_processed: # 第一次访问当前节点,加入路径 path.append(mat[i][j]) # 到达终点,输出路径 if i == M - 1 and j == N - 1: print(path.copy()) # 直接回溯当前节点 path.pop() continue # 先压入带已处理标记的当前节点,等子节点全部处理完后执行回溯 stack.append((i, j, True)) # 压入合法子节点,顺序与原递归的调用顺序相反(栈后进先出,保证弹出顺序一致) # 原递归处理顺序:右→下→对角,因此压栈顺序为:对角→下→右 # 压对角方向(最后处理) if 0 <= i + 1 < M and 0 <= j + 1 < N: stack.append((i + 1, j + 1, False)) # 压向下方向(中间处理) if 0 <= i + 1 < M and 0 <= j < N: stack.append((i + 1, j, False)) # 压向右方向(最先弹出,最先处理) if 0 <= i < M and 0 <= j + 1 < N: stack.append((i, j + 1, False)) else: # 已处理完所有子节点,回溯弹出当前节点 path.pop() if __name__ == '__main__': mat = [ [1, 2, 6], [4, 5, 7], [7, 8, 9] ] findPathsIter(mat)
BFS迭代版(适合逐行遍历场景)
如果不需要对齐原递归的输出顺序,也可以用队列实现BFS,每个节点存储对应走到该点的路径:
from collections import deque def findPathsBFS(mat): M, N = len(mat), len(mat[0]) # 队列元素格式: (当前行i, 当前列j, 走到当前点的路径) q = deque() q.append((0, 0, [mat[0][0]])) all_paths = [] while q: i, j, path = q.popleft() # 到达终点,存入结果 if i == M - 1 and j == N - 1: all_paths.append(path) continue # 右移动 if j + 1 < N: q.append((i, j + 1, path + [mat[i][j + 1]])) # 下移动 if i + 1 < M: q.append((i + 1, j, path + [mat[i + 1][j]])) # 对角移动 if i + 1 < M and j + 1 < N: q.append((i + 1, j + 1, path + [mat[i + 1][j + 1]])) # 打印所有路径 for p in all_paths: print(p) return all_paths
注意:BFS版本每个节点都要存储一份路径副本,空间复杂度更高,适合需要找最短路径、逐行遍历的场景;如果只是输出所有路径并保持原逻辑,优先使用DFS迭代版,调整规则(比如加障碍物判断、修改移动方向、过滤特定路径)更方便。
内容的提问来源于stack exchange,提问作者sdsg346dfg
相关产品推荐
相关产品推荐

