我該如何擺脫這個遞歸循環？

Question

我還是一個Python的新手，所以請容忍我糟糕的語法和邏輯，如果有什麼不好的。無論如何，我有一個函數，我試圖乾淨地（沒有花哨的動作請）打破了遞歸循環。它是程序中的一個函數，它通過1和0的遞歸迭代（請參見下面的輸入文件），並將相鄰的0識別爲不同的子集。我有一個名爲「checkAllInOneDirection」的遞歸函數，它將遍歷每個位置，向右，向左，向上，向下位置循環以檢查0。 （對於每個遞歸，它只在四個方向中的每一個上進一步深入/進一步）。

這個問題是由於某些原因，第三組的輸出應該只檢測到0,9和0,10作爲一個不同的集合，但是當第二組檢測後它退出遞歸時，它會拾取[0,4 ]和[1,3]在第三組檢查的開始...任何幫助？

這是輸出[行，列]：

Distinct subset found : [[0, 0]] 
Distinct subset found : [[0, 3], [0, 4], [1, 3], [0, 5], [1, 4], [1, 5]] 
Distinct subset found : [[0, 9], [0, 4], [1, 3], [0, 10]] 

正確第三子集應該只有：

Distinct subset found : [[0, 9], [0, 10]] 

這裏的一個示例輸入文件：

01100011100100000 
11100011111111011 
10011111101011011 

這裏的該函數的一個片段，它被稱爲「checkAllInOneDirection」：

isItLast = checkLast(forBoo, bakBoo, upBoo, dwnBoo) 
if isItLast: 
    for each in tempCatch: 
     if not each in finalCatch: 
      finalCatch.append(each) 
    tempCatch=[] 
    for each in newCatch: 
     if not each in finalCatch: 
      finalCatch.append(each) 
    newCatch=[] 
    return finalCatch, newCatch, columnCount, rowCount, width, height, posToCheck, forBoo, bakBoo, upBoo, dwnBoo 
else: 
    for each in tempCatch: 
     if not each in finalCatch: 
      finalCatch.append(each) 
    tempCatch =[] 
    for each in newCatch:  
     if not each in finalCatch: 
      finalCatch.append(each) 
      tempCatch.append(each) 
    newCatch = [] 

return checkAllInOneDirection(finalCatch,tempCatch,recursiveCount,newCatch, columnCount, rowCount, width, height, posToCheck, forBoo, bakBoo, upBoo, dwnBoo)  

這裏就是整個功能，希望它只是闡明不會讓我的問題更多的困惑：

def checkAllInOneDirection(finalCatch,tempCatch,recursiveCount,newCatch, columnCount, rowCount, width, height, posToCheck, forBoo, bakBoo, upBoo, dwnBoo): 
    for each in range (0, len(tempCatch)): 
     posToCheck = posToCheckBak = posToCheckUp = posToCheckDwn = [tempCatch[each][0], tempCatch[each][1]] 
     newPosForward = checkForward(posToCheck, width) 
     if newPosForward != False: 
      tempLocale = locale[newPosForward[0]][newPosForward[1]] 
     elif newPosForward == False: 
      tempLocale = 1 
     if newPosForward != False and tempLocale ==0 and not newPosForward in finalCatch and not newPosForward in newCatch: 
      forVal = locale[newPosForward[0]][newPosForward[1]] 
      newCatch.append(newPosForward) 
      posToCheck = newPosForward 
      forBoo = True 
     elif newPosForward == False and tempLocale == 1 and not newPosForward in newCatch: 
      forBoo = False 

     newPosBackward = checkBackward(posToCheckBak) 
     if newPosBackward != False: 
      tempLocale = locale[newPosBackward[0]][newPosBackward[1]] 
     elif newPosBackward == False: 
      tempLocale = 1  
     if newPosBackward != False and tempLocale ==0 and not newPosBackward in finalCatch and not newPosBackward in newCatch: 
      forVal = locale[newPosBackward[0]][newPosBackward[1]] 
      newCatch.append(newPosBackward) 
      posToCheckBak = newPosBackward 
      bakBoo = True 
     elif newPosBackward == False and tempLocale == 1 and not newPosBackward in newCatch: 
      bakBoo = False 

     newPosUp = checkUpRow(posToCheckUp) 
     if newPosUp != False: 
      tempLocale = locale[newPosUp[0]][newPosUp[1]] 
     elif newPosUp == False: 
      tempLocale = 1 
     if newPosUp != False and tempLocale ==0 and not newPosUp in finalCatch and not newPosUp in newCatch: 
      forVal = locale[newPosUp[0]][newPosUp[1]] 
      newCatch.append(newPosUp) 
      posToCheckUp = newPosUp 
      upBoo = True 
     elif newPosUp == False and tempLocale == 1 and not newPosUp in newCatch: 
      upBoo = False 

     newPosDwn = checkDwnRow(posToCheckDwn, height) 
     if newPosDwn != False: 
      tempLocale = locale[newPosDwn[0]][newPosDwn[1]] 
     elif newPosDwn == False: 
      tempLocale = 1 
     if newPosDwn != False and tempLocale ==0 and not newPosDwn in finalCatch and not newPosDwn in newCatch: 
      forVal = locale[newPosDwn[0]][newPosDwn[1]] 
      newCatch.append(newPosDwn) 
      posToCheckDwn = newPosDwn 
      dwnBoo = True 
     elif newPosDwn == False and tempLocale == 1 and not newPosDwn in newCatch: 
      dwnBoo = False 

    isItLast = checkLast(forBoo, bakBoo, upBoo, dwnBoo) 
    if isItLast: 
     for each in tempCatch: 
      if not each in finalCatch: 
       finalCatch.append(each) 
     tempCatch=[] 
     for each in newCatch: 
      if not each in finalCatch: 
       finalCatch.append(each) 
     newCatch=[] 
     return finalCatch, newCatch, columnCount, rowCount, width, height, posToCheck, forBoo, bakBoo, upBoo, dwnBoo 
    else: 
     for each in tempCatch: 
      if not each in finalCatch: 
       finalCatch.append(each) 
     tempCatch =[] 
     for each in newCatch:  
      if not each in finalCatch: 
       finalCatch.append(each) 
       tempCatch.append(each) 
     newCatch = [] 

    return checkAllInOneDirection(finalCatch,tempCatch,recursiveCount,newCatch, columnCount, rowCount, width, height, posToCheck, forBoo, bakBoo, upBoo, dwnBoo)  

Answer 1

當使用遞歸時，你真的不應該使用像「循環」和「中斷」這樣的短語。相反，把這個問題看作是由類似的子問題組成，這些問題在基本情況下變得微不足道。

您的一般問題是找到0的其他0的旁邊。 （順便說一句，這叫做4-direction flood fill。）所以更大的問題有相同的子問題;所有連接的0列表的相同的組合：

• 只是含有一個單一的‘開始點’0
• 包含所有0的列表的列表的至右側「開始點」 0
• 包含所有0的列表的至‘開始點’的左側0
• 包含所有0的列表的‘開始點’0
012以上
• 包含所有0年代的‘起點’0

所以在您的遞歸函數的地方下面的列表，你有話的大意是：

return [[y,x]] + getConnectedZeros(x+1, y) + getConnectedZeros(x-1, y) + getConnectedZeros(x, y+1) + getConnectedZeros(x, y-1) 

知道這，那麼你需要考慮一下你的基本情況，其中getConnectedZeros()將不得不返回一些不同於其子問題解決方案組合的情況。對我來說，基本情況是：

• 當函數被調用上包含1
• 當函數被調用在0一個地方，已經被「發現」

對於這兩種情況下，只要返回一個空列表就可以工作，因爲當返回[]時，它代替了更多的遞歸調用。如果這些條件不包括在內，那麼遞歸將永遠運行，並且從不打中斷命中一個基本情況。

基於這些想法，這裏是你的問題的解決方案：

sampleInput = "01100011100100000\n11100011111111011\n10011111101011011" 
inputMatrix = [[int(n) for n in row] for row in sampleInput.split('\n')] #matrix where each row is a list of the numbers from sampleInput 

def getConnectedZeros(matrix, x, y, foundIndicies=[]): 
    if 0<=y<len(matrix) and 0<=x<len(matrix[y]): #catch out of bounds 
     if matrix[y][x] == 1: #catch 1s 
      return [] 
     else: 
      if not (x,y) in foundIndicies: #catch 0's we've already "seen" 
       foundIndicies.append((x,y)) 
       return [[y,x]] + getConnectedZeros(matrix, x+1, y, foundIndicies) + getConnectedZeros(matrix, x-1, y, foundIndicies) + getConnectedZeros(matrix, x, y+1, foundIndicies) + getConnectedZeros(matrix, x, y-1, foundIndicies) 
      else: 
       return [] 
    else: 
     return [] 


#Now we can just loop through the inputMatrix and find all of the subsets 
foundZeroIndicies = [] 
subsets = [] 
y = -1 
for row in inputMatrix: 
    y += 1 
    x = -1 
    for val in row: 
     x += 1 
     if (not [y,x] in foundZeroIndicies) and val==0: 
      zerosList = getConnectedZeros(inputMatrix, x, y) 
      subsets.append(zerosList) 
      foundZeroIndicies.extend(zerosList) 
for subset in subsets: 
    print "Distinct Subset Found : ", subset 

希望幫助一些。 （並希望它是連貫的，這是凌晨5點...）

Answer 2

打破遞歸的，你需要使用的回報。如果你的遞歸繼續下去，你需要重新考慮你的基本情況。

只是爲了好玩我嘗試使用networkx這一點，並不在於它回答你的問題：

data = """01100011100100000 
11100011111111011 
10011111101011011""".splitlines() 

import networkx 

G = networkx.Graph() 
found = set() 

for i, row in enumerate(data): 
    for j, c in enumerate(row): 
     if c == '0': 
      found.add((i, j)) 
      if i + 1 < len(data) and data[i + 1][j] == '0': 
       G.add_edge((i, j), (i + 1, j)) 
      if j + 1 < len(row) and row[j + 1] == '0': 
       G.add_edge((i, j), (i, j + 1)) 

groups = map(list, networkx.connected_component_subgraphs(G)) 
group_nodes = set(node for group in groups for node in group) 
individuals = found - group_nodes 

print groups 
print individuals 

""" 
[[(0, 15), (0, 14), (1, 14), (0, 13), (0, 12), (0, 16), (2, 14)], [(1, 3), (1, 4), (1, 5), (0, 5), (0, 4), (0, 3)], [(2, 1), (2, 2)], [(0, 9), (0, 10)]] 
set([(0, 0), (2, 11), (2, 9)]) 
""" 

Answer 3

我的代碼是一個使用遞歸函數的步行路程的一個例子（）。我希望它能幫助你解決問題。

input = ['01100011100100000', 
     '11100011111111011', 
     '10011111101011011'] 
col_len = 17 
row_len = 3 

walked = [] 
output = [] 

def walk(subset_in, row, col): 
    if (0 <= row < row_len) and (0 <= col < col_len) and (row, col) not in walked: 
     walked.append((row, col)) 
     if input[row][col] == '0': 
      if subset_in is not None: 
       subset = subset_in 
      else: 
       subset = [] 

      subset.append((row, col)) 
      walk(subset, row, col+1) 
      walk(subset, row+1, col) 
      walk(subset, row, col-1) 
      walk(subset, row-1, col) 

      if subset_in is None: 
       output.append(subset) 

for row in xrange(row_len): 
    for col in xrange(col_len): 
     if (row, col) not in walked: 
      walk(None, row, col) 

for subset in output: print subset