递归导致不必要的循环

Question

我在使用递归时遇到一些困难。下面，我有一段代码试图解决一个难题。 process() 生成排列，然后 solve() 遍历这些排列并检查每个排列。如果解决方案在某个位置失败，则该函数会删除所有以相同方式开始的可能解决方案，并递归地重新运行。 test_it() 函数在 solve() 中被调用，作为确定解决方案何时不正确的一种方式。

这最终给出了正确的结果，但是当我添加打印行时：

print 'Fail', combo, count

我注意到函数似乎识别了正确的解决方案，但随后仍然继续迭代。我想我可能把嵌套循环弄乱了，因为一旦它到达行：

return combo

它不会终止。

import itertools

final_side = [{(1,2): [[1,0,1,1]]},\
              {(2,1): [[1,1,0,1]]},\
              {1: [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]},\
              {1: [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]}]

final_top = [{2: [[1,1,0,0],[0,1,1,0],[0,0,1,1]]},\
              {(1,1): [[1,0,1,0],[1,0,0,1],[0,1,0,1]]},\
              {(1,1): [[1,0,1,0],[1,0,0,1],[0,1,0,1]]},\
              {2: [[1,1,0,0],[0,1,1,0],[0,0,1,1]]}]

def process():
    # Generates all permutations
    possible = []
    possibilities = []
    a = []

    for dic in final_side:
        for values in dic.values():
            possible.append(len(values))            

    for number in possible:
        a.append([x for x in range(number)])

    b = map(list, itertools.product(*a))

    return b

def test_it(listx, final_top, final_side):

    length = len(listx)
    place = []    

    if length > 0:
        pot = map(list, zip(*listx))
        for j in range(len(pot)):
            x = final_top[j].values()[0]
            test = [x[i][:length] for i in range(len(x))]

            if pot[j] not in test:
                return False

            else:
                loc = [x for x,val in enumerate(test) if val== pot[j]]
                place.append(loc)
    return place


def solve(listx):

    solution = []     

    for combo in listx[:]:
        pos = -1
        temp = []
        count = 0
        for num in combo:
            pos += 1
            temp.append(final_side[pos].values()[0][num])
            place = test_it(temp, final_top, final_side)    

            if place == False:
                blah = combo[:pos+1]
                listx = [x for x in listx if not x[:pos+1] == combo[:pos+1]]
                print 'Fail', combo, count                 
                solve(listx)

            else:
                count += 1
                if count == 4:
                    return combo

def main():


    a = process()
    solution = solve(a)

    print solution

main()

Answer 1

您正在忽略递归调用的 return 值：

if place == False:
    blah = combo[:pos+1]
    listx = [x for x in listx if not x[:pos+1] == combo[:pos+1]]
    print 'Fail', combo, count                 
    solve(listx)

那里的solve()调用的return值被丢弃了；它不会传递给下一个调用者，您也不会在那里结束循环。

添加一个 return 以退出该级别的递归调用：

if not place:
    blah = combo[:pos+1]
    listx = [x for x in listx if not x[:pos+1] == combo[:pos+1]]
    print 'Fail', combo, count                 
    return solve(listx)

我还将 place == False 替换为 not place，这是一种更好的测试布尔值 false 的方法。

通过这些更改，您的脚本输出：

$ bin/python test.py 
Fail [0, 0, 0, 0] 2
Fail [0, 0, 1, 0] 2
Fail [0, 0, 2, 0] 3
[0, 0, 2, 1]

递归导致不必要的循环

Recursion results in unwanted looping

python

recursion

loops