如何编写递归函数查找矩阵中指定数字的所有坐标位置

核心逻辑 #

这题本质是把双层遍历的逻辑改成递归实现，不需要复杂的搜索算法，只要靠递归推进行、列两个索引，逐格检查值是否匹配就行，哪怕是不规则矩阵（每行长度不一致）也能兼容。
递归不需要多余参数，只要跟踪两个核心状态即可：当前检查的行索引、当前行内检查的列索引，匹配到的坐标统一存在结果列表里就行。

分步实现逻辑 #

按顺序写代码即可，不用上来就凑完整逻辑：

• 先写外层入口函数：初始化空结果列表，启动递归时从矩阵左上角(0,0)位置开始检查，递归跑完直接返回结果列表
• 再按优先级写递归的终止边界：
  • 如果当前行索引已经等于矩阵总长度，说明所有格子都检查完了，直接终止递归
  • 如果当前列索引已经等于当前行的总长度，说明当前行已经扫完，递归调用自身把行索引+1、列索引重置为0，开始扫下一行，这步执行完直接return，不要继续往下执行
• 然后写当前格子的检查逻辑：如果当前位置的值等于待查找目标，就把(当前行索引, 当前列索引)的元组追加到结果列表里
• 最后写递归推进逻辑：不管当前值匹不匹配，都保持行索引不变，列索引+1，递归检查同一行的下一个格子

参考代码结构 #

def find_number_positions(matrix, target_num):
    result = []
    def recursive_search(row, col):
        # 所有行遍历完成，终止递归
        if row == len(matrix):
            return
        # 当前行遍历完成，跳转下一行开头
        if col == len(matrix[row]):
            recursive_search(row + 1, 0)
            return
        # 匹配到目标值，记录坐标
        if matrix[row][col] == target_num:
            result.append((row, col))
        # 检查当前行下一个元素
        recursive_search(row, col + 1)
    
    # 从(0,0)位置启动递归
    recursive_search(0, 0)
    return result

# 测试示例输入
matrix = [[2,0,1],[3,5,3],[5,1,4,9],[0,5]]
numberToFind = 5
print(find_number_positions(matrix, numberToFind))
# 输出：[(1, 1), (2, 0), (3, 1)] 和预期结果一致

注意避坑 #

• 不要默认矩阵每行长度相等，判断列边界时必须取当前行的长度len(matrix[row])，不能用第一行长度代替，不然不规则矩阵会报索引越界
• 跳转下一行的递归调用执行完一定要加return，不然代码会继续往下执行列+1的逻辑，同样会触发越界
• 坐标元组的顺序是（行索引, 列索引），别写反顺序导致结果不符合要求

内容的提问来源于stack exchange，提问作者theJohnLewis