如何摆脱这种递归循环？ [英] How do I break out of this recursive loop?

问题描述

我仍然是Python的新手，因此，如果有任何不好的语法和逻辑，请忍受。无论如何，我有一个函数正在尝试清除（请不要花哨的动作）打破递归循环。它是程序中的一个函数，它递归地迭代1和0（请参见下面的输入文件），并将相邻的0标识为不同的子集。我有一个称为 checkAllInOneDirection的递归函数，该函数将循环遍历每个位置，向右，向左，向上，向下位置检查0。 （每次递归在4个方向中的每个方向上仅向左/向左/向下移动。）

I'm still a newbie in Python, so please tolerate my poor syntax and logic if any were bad. Anyhow, I have a function that I'm trying to cleanly (no fancy moves please) break out of a recursive loop. It's a function in a program that iterate through recursively of 1s and 0s (see input file below), and identify the adjacent 0s as distinct subsets. I have a recursive function called "checkAllInOneDirection" that will loop through each position, going right, left, up, down positions to check for 0s. (It goes only one left deep/further on each of the 4 directions for each recursion).

问题是由于某种原因，第三组的输出应仅检测到0 ，9和0,10作为一个不同的集合，但是当在第二个集合检测之后它又从递归中跳出时，它在检查第三个集合的开始时拾取了[0，4]和[1，3]。

The problem is for some reason the output of third set should detect only 0,9 and 0,10 as one distinct set but when it breaks out of the recursive after the second set detection, it picked up [0, 4] and [1, 3] at the beginning of the check of the third set... Any help?

这是输出[行，列]：

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

正确的第三子集应该仅是：

The correct third subset should be only :

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

样本输入文件：

01100011100100000
11100011111111011
10011111101011011

这是该函数的代码段，它是称为 checkAllInOneDirection：

Here's a snippet of the function, it's called "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)    

这里是整个函数，希望它只是澄清一下，不要让我的问题更令人困惑：

Here's the entire function, hope it only clarifies not make my question any more confusing:

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)    

推荐答案

使用递归时，您实际上不应该使用诸如循环和中断之类的短语。取而代之的是，将问题视为由在基本案例中变得无关紧要的类似子问题组成。

When using recursion, you really shouldn't be using phrases like "loop" and "break." Instead, think of the problem as consisting of similar subproblems that become trivial at the base cases.

您的一般问题是找到与其他 0相邻的 0 个。 （顺便说一下，这称为 4向洪水填充。）因此，更大的问题是相同的子问题；所有连接的 0 的列表与以下各项的组合相同：

Your general problem is to find 0's that are next to other 0's. (This is called a 4-direction flood fill, by the way.) So the larger problem has identical subproblems; the list of all the connected 0's is the same as the combination of:

• 仅包含一个起点的列表 0


• 包含所有 0的列表位于起点右侧 0


• 包含所有 0 位于起点左侧 0


• a包含所有在起点上方的 0 的列表 0


• 包含所有在起点以下的 0 的列表 0

• a list just containing a single "start point" 0
• a list containing all of the 0's to the right of the "start point" 0
• a list containing all of the 0's to the left of the "start point" 0
• a list containing all of the 0's above the "start point" 0
• a list containing all of the 0's below the "start point" 0

因此，在递归函数中的某处，您将产生以下效果：

So somewhere in your recursive function, you'll have something to the effect of:

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

知道这一点后，您需要考虑一下基本情况，即 getConnectedZeros（）必须返回与其子问题解决方案组合不同的东西。对我来说，基本情况是：

Knowing this, you need to then think about your base cases, the cases where getConnectedZeros() will have to return something different than the combination of its subproblems' solutions. To me, the base cases are:

• 在包含 1


• 在已被找到的 0 上调用函数时

• when the function is called on a place containing a 1
• when the function is called on a 0 that has already been "found"

对于这两种情况，简单地返回一个空列表都是可行的，因为返回 [] 时，它位于递归调用的地方。如果不包括这些条件，则递归将永远运行，并且永远不会 break 达到​​基本情况。

For both cases, simply returning an empty list will work since when [] is returned, it is in place of more recursive calls. If these conditions were not included, then the recursion would run forever, and never break hit a base case.

基于这些想法，这里是解决您的问题的方法：

Based on those ideas, here is a solution to your problem:

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点...）

Hopefully that helps some. (And hopefully it was coherent, it's 5 am here...)

这篇关于如何摆脱这种递归循环？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！