You need to enable JavaScript to run this app. 如何将查找矩阵从左上到右下全路径的递归函数转换为迭代函数?
优惠活动
大模型
产品
解决方案
定价
更多

如何将查找矩阵从左上到右下全路径的递归函数转换为迭代函数?

递归转迭代的实现方案

递归转迭代的核心是手动模拟系统调用栈的状态,处理好递归的后序回溯操作(也就是原函数里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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.05 04:06:09