如何将寻找矩阵中所有可能路径的递归函数转换为迭代函数？

将递归函数转换为迭代函数通常涉及到使用数据结构（如栈）来模拟递归调用的行为。下面是一个示例，展示如何将一个寻找矩阵中所有可能路径的递归函数转换为迭代函数。

递归版本

假设我们有一个矩阵，从左上角到右下角的所有路径都需要被找到。递归版本的代码可能如下：

def find_all_paths_recursive(matrix, x, y, path, all_paths):
    if x == len(matrix) - 1 and y == len(matrix[0]) - 1:
        all_paths.append(path + [(x, y)])
        return
    
    # Mark the current cell as visited
    temp = matrix[x][y]
    matrix[x][y] = -1
    
    # Explore all possible directions: right, down, left, up
    for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]) and matrix[nx][ny] != -1:
            find_all_paths_recursive(matrix, nx, ny, path + [(x, y)], all_paths)
    
    # Unmark the current cell
    matrix[x][y] = temp

def find_all_paths(matrix):
    all_paths = []
    find_all_paths_recursive(matrix, 0, 0, [], all_paths)
    return all_paths

迭代版本

我们可以使用栈来模拟递归调用的行为：

def find_all_paths_iterative(matrix):
    if not matrix or not matrix[0]:
        return []
    
    all_paths = []
    stack = [([(0, 0)], 0, 0)]
    
    while stack:
        path, x, y = stack.pop()
        
        if x == len(matrix) - 1 and y == len(matrix[0]) - 1:
            all_paths.append(path + [(x, y)])
            continue
        
        # Mark the current cell as visited
        temp = matrix[x][y]
        matrix[x][y] = -1
        
        # Explore all possible directions: right, down, left, up
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]) and matrix[nx][ny] != -1:
                stack.append((path + [(x, y)], nx, ny))
        
        # Unmark the current cell
        matrix[x][y] = temp
    
    return all_paths