递归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):

……等等，9次。你知道吗

然后我意识到同样的事情也可以用两个递归函数来完成，这两个函数将尝试一个片段，而不是正确地调用第二个函数，然后成功地引用第一个函数！你知道吗

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] = [];

第二个函数与第一个函数相同（除了调用第一个函数）。你知道吗

这段代码的问题是它总是过早结束，而且Solved（）永远不会被调用。你知道吗

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

有没有办法在for循环中递归调用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不是全局可访问的，则可以将其作为另一个输入添加到函数中，并在进行递归调用时将其向下传递。你知道吗

如果你真的对递归感兴趣，可以看看麻省理工学院的stellarStructure and Interpretation of Computer Programs课程。在那个链接上可以免费获得整本书。我一直在Racket中研究它，我也不介意推荐它。你知道吗

编辑：从我们在注释中的讨论来看，似乎每个递归级别都需要检查上一级别是否返回了有效的解决方案，或者只是停止了而没有找到解决方案，然后将有效的解决方案传递给上一级，或者相应地继续其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循环的下一次迭代。如果这能帮你找到你要去的地方，请告诉我。你知道吗