递归搜索二维列表中的特定元素

Question

这个叫做 findStart() 的函数是用来在一个二维列表中递归搜索的，这个列表代表了一个迷宫。它的任务是查找这个列表中一个特定元素 "S" 的位置，也就是它的 x 和 y 坐标（分别是第一个和第二个索引）。不过，这个函数需要使用递归，而且 findStart() 方法不应该接受任何参数。我已经知道怎么用循环来实现这个功能，但我该如何把这个循环改成递归呢？

def findStart():
    for a in mazeList:
        for x in a:
            if x == "S":
                xcoord = a.index("S")
                ycoord = mazeList.index(a)
                return (ycoord),(xcoord)
    return -1,-1

迷宫：

####################################
#S#  ##  ######## # #      #     # #
# #   #             # #        #   #
#   # ##### ## ###### # #######  # #
### # ##    ##      # # #     #### #
#   #    #  #######   #   ###    #E#
####################################

Answer 1

首先，我同意上面评论讨论的观点：在 Python 中对没有参数的函数进行递归搜索并不是一个好主意，因为这可能会导致一些问题，具体取决于你的搜索方式以及它如何访问你的 global 变量。实际上，你是在做一个由函数“控制”的迭代搜索，也就是说，函数只是决定什么时候增加计数。

要按照你描述的方式正确进行迭代搜索，你可以把 findStart 变成一个包装函数：

可以选择（推荐）：

def findStart(mazeList):
    return findStartRec(mazeList,0,0)

或者：

mazeList = ... # 定义 mazeList def findStart(mazeList): return findStartRec(mazeList,0,0)

然后解决问题：

def findStartRec(mazeList,x,y):
    if y >= len(mazeList):
        return -1,-1                         # We have reached the end of the maze and no result
    if x >= len(mazeList[y]):
        return findStartRec(mazeList,0,y+1)  # We have reached the end of a row, continue to the next row
    if mazeLise[y][x] == "S":
        return x,y                           # We have found the start
    else:
        return findStartRec(mazeList,x+1,y)  # Search the next spot on this row

对我来说，这样可以：

>>> findStartRec(mazeList) 
(1, 1)

然后先定义一个没有参数的函数：

maze = """####################################
#S#  ##  ######## # #      #     # #
# #   #             # #        #   #
#   # ##### ## ###### # #######  # #
### # ##    ##      # # #     #### #
#   #    #  #######   #   ###    #E#
####################################"""
mazeList = [[x for x in row] for row in maze.split('\n')]
def findStart():
    return findStartRecu(mazeList,0,0)

接着调用：

>>> findStart()
(1,1)  

最后要说明的是，这其实不是递归搜索的最佳应用场景，因为这个搜索是在非常明确且已知的范围内进行的，也就是说，它是矩形的。递归搜索更适合用于树、链表等非线性结构的数据，因为用像 for 循环这样的有限映射来搜索它们是不可行的。