如何打破这个递归循环？

Question

我仍然是Python的新手，所以请容忍我糟糕的语法和逻辑。不管怎样，我有一个函数，我正在尝试干净地（请不要花哨的移动）打破一个递归循环。它是程序中的一个函数，它递归地遍历1和0（参见下面的输入文件），并将相邻的0标识为不同的子集。我有一个名为“checkAllInOneDirection”的递归函数，它将循环遍历每个位置，从右、左、上、下位置检查0（对于每个递归，它只在4个方向上向左深/再向前）。在

问题是由于某种原因，第三个集合的输出应该只检测0，9和0，10作为一个不同的集合，但当它在第二个集合检测后跳出递归时，它在第三个集合的检查开始时选取了[0，4]和[1，3]。。。有什么帮助吗？在

这是输出[row，column]：

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

正确的第三个子集应仅为：

^{pr2}$

以下是输入文件示例：

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

要打破递归，需要使用return。如果递归继续进行，则需要重新考虑基本情况。在

只是为了好玩，我试着用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 2

我的代码是使用递归函数walk（）的示例。我希望它能帮助你解决问题。在

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

Answer 3

当使用递归时，你真的不应该使用像“loop”和“break”这样的短语，而应该把问题看作是由类似的子问题组成的，这些子问题在基本情况下变得微不足道。在

您的一般问题是找到与其他0相邻的0（顺便说一下，这称为4-direction flood fill）。因此较大的问题具有相同的子问题；所有连接的0的列表与以下内容的组合相同：

• 只包含一个“起点”的列表0
• 在“起点”0右侧包含所有0的列表
• 在“起点”0左侧包含所有0的列表
• 包含“起点”0上方所有0的列表
• 包含“起点”0以下所有0的列表

因此，在递归函数的某个地方，您将得到如下效果：

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

了解了这一点，您需要考虑您的基本情况，getConnectedZeros()将必须返回与子问题解决方案组合不同的内容。对我来说，基本情况是：

• 在包含1的地方调用函数时
• 在已“找到”的0上调用函数时

对于这两种情况，只要返回一个空列表就可以了，因为当[]被返回时，它代替了更多的递归调用。如果不包括这些条件，则递归将永远运行，并且永远不会中断达到基本情况。在

基于这些想法，这里有一个解决问题的方法：

^{2}$

希望这能帮助一些人。（希望是连贯的，现在是凌晨5点…）