以递归方式搜索特定元素的2D列表

称为findStart（）的函数假设是递归地搜索代表迷宫的二维列表。假设搜索这个列表并找到列表中某个特定元素的“第一个和第二个索引”为“S”。然而，它假设使用递归，并且findStart（）方法不接受任何参数。我已经发现如何通过迭代来实现它，但是我怎样才能使这个迭代进入递归？以递归方式搜索特定元素的2D列表

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# 
####################################

来源

2014-03-28 user3373360

这些是一些非常奇怪的要求。如果一个函数没有参数，你如何确定递归的终止条件？你必须使用全局变量。似乎更麻烦，而不是只是迭代地找到坐标。 – Kevin

您可以简单地创建一个执行递归的第二个（甚至是内部）函数。 –

我对Python并不十分熟悉，但递归确实需要传入某种参数（除非您使用全局变量，但这是一种坏习惯IMO）。然后使用该参数来确定函数是否需要再次递归调用。我认为这样做的唯一方法是创建第二个方法，它调用findStart（）方法，而第二个方法是递归方法（第二种方法当然有参数，可能是下一个坐标）。 –

现在，前言本我与上面上没有参数的函数在Python这样做递归搜索的注释讨论同意不建议，因为你可能会遇到的问题取决于关于你的搜索是如何工作的以及它如何访问你的变量，你基本上会做一个迭代搜索，这个迭代搜索由一个函数“管理”，也就是说它决定什么时候增加以及什么时候增加。

要正确地做到在时装你描述你可以把findStart成包装函数迭代搜索：

或者（reccomended）：

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

或： mazeList = ...＃定义mazeList 高清findStart（mazeList）：返回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)

最后要注意的，这不是真正的递归搜索的最佳应用，因为这个搜索e xists在非常确定的和已知的范围内，即它是矩形的。递归搜索更适合于诸如树，链表等数据结构的非线性形状，因为使用有限映射如for循环无法真正搜索它们。

来源

2014-03-28 17:46:33

以递归方式搜索特定元素的2D列表

回答

相关问题