递归Python方法

Question

我正在编写一个程序来解决一种正方形的谜题，它用蛮力尝试每一个可能的组合，直到它找到一些有用的东西。

董事会看上去像这样

1-2-3

4-5-6

7-8-9

我从一堆嵌套的for循环开始，

 for a in range(1,10):
     #create piece
     #than test it
     if checkPiece(pieceNumber):
          for b in range (1,10):

...and等等，九次。

然后，我意识到同样的事情可以用两个递归函数来完成，如果正确调用第二个函数，那么第二个函数就会成功地引用第一个函数。

def Solve():
    global level;
    global AvailableNumbers;
    if level == 10:
        Solved();
    for i in AvailableNumbers:
        print "We are %d far into level %d with fct. ONE" %(i,level);
        clearList(level);
        AvailableNumbers.remove(i)
        spot[level] = pieces[i];
        result = checkPiece(level)
        print result
        if result == True:
            level += 1
            Solve2();
        else:
            AvailableNumbers.append(i);
            spot[level] = [];

第二个函数与第一个函数相同(除了调用第一个函数外)。

这段代码的问题是，它总是过早地结束，解决()永远不会被调用。

我怀疑，当一个方法被调用时，它可能会覆盖该方法以前的任何活动(从而结束我的递归梦想)，但不能确定我的代码中是否还有其他错误。

有没有办法递归调用for循环内部的循环，

(不是为了{}，而是为了{}})

而不用把它全写出来？

谢谢你看了这么多。任何帮助都将不胜感激！

Answer 1

我会尝试以下几种方法：

def Solve(level, available_numbers):
  if level == 10:
    return spot
  for i in available_numbers:
    print "We are %d far into level %d with fct. ONE" %(i,level)
    clearList(level)
    # Note you are not removing i from available_numbers yet
    spot[level] = pieces[i]
    result = checkPiece(level)
    print result
    if result == True:
      available_number = available_number.remove(i)
      Solve(level + 1, available_number)  # tail recursion!

    # note no need for your else statement. We haven't removed i from our list yet,
    # and we can just overwrite spot[level] on the next pass.

如果没有剩下的代码，我就无法测试它，但是基本的思想是使用递减的数字池调用Solve函数的递归迭代，直到您在一个可以工作的位置上有了每个数字为止。我假设spot是您的解决方案向量，所以在最后，我们返回spot，它从链上传回到顶部并输出。如果spot不是全局访问的，您可以将它作为另一个输入添加到您的函数中，并在进行递归调用时将它传递到行中。

如果你真的对递归感兴趣，请看麻省理工学院的恒星计算机程序的结构与解释课程。整本书在那个链接上是免费的。我一直在球拍中工作，我也不介意推荐它。

编辑:根据我们在注释中的讨论，听起来每个级别的递归都需要检查以前的级别是返回了一个有效的解决方案，还是只是在没有找到解决方案的情况下就停止了，然后将有效的解决方案传递到相应的for循环的下一个迭代中。也许是这样的？

def Solve(level, nums, spot):
  if level = 10:  # maybe check if nums = [] for an arbitrary number of levels?
    return (spot, True)  # pass back solution and Boolean saying it's solved
  for i in nums:
    # place your next piece
    result = checkPiece(level)
    if result:  # no need for the "== True" bit
      nums = nums.remove(i)
      spot, solved = Solve(level + 1, nums, spot)  # recursive call
      if solved:  # valid solution reached?
        return (spot, solved)  # pass new solution up the chain
      # else continue to the next iteration of the for loop
  return (spot, False)  # reach this if no valid solution is found at this level

关键的变化是，除了传递一个布尔值，它告诉我们是否已经达到了有效的解决方案，现在我们还显式地将更新的解决方案向量传递到链上。您还可以检查解决方案在每个级别上是否有效，但这似乎不太有效。如果任何级别的for循环都用完了，我们就返回solved = False，这会让我们跳到下一个更高级别的for循环的下一个迭代。如果这能让你找到你需要去的地方就告诉我。