以遞歸方式搜索特定元素的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列表

回答

相關問題