修复Python递归会导致错误的结果

Question

我认为我的代码没有问题，但是当我开始更改值时，最终导致了递归问题。我以为我修好了它，但是当我看到结果时，他们都是错的。当我保持递归时，结果很好。

我使用了一个while循环来尝试修复递归问题，而不是递归调用spread方法，而是返回值传递给propagate方法，并返回False，如果它不通过值。所以，只要该方法保持返回值，它应该重新运行传播方法和前一次运行的结果。

此代码的工作，直到它打破递归限制：

def spread(self, position): 
     for direction in self._directions: 
      (x, y) = self.changePosition(position, direction) 
      if self.canInfectMatrix[x][y] and not self.contactMatrix[x][y]: 
       self.contactMatrix[x][y] = True 
       self.spread([x,y]) 
#     return [x,y] 
#    return False 

    def propagate(self): 
     # initialize canInfectMatrix and contactMatrix 
     self.contactMatrix = [[False for row in range(self.cardinalWidth)] for col in range(self.cardinalWidth)] 
     self.canInfectMatrix = [[False for row in range(self.cardinalWidth)] for col in range(self.cardinalWidth)] 
     for col in range(self.cardinalWidth): 
      for row in range(self.cardinalWidth): 
       self.canInfectMatrix[row][col] = self.getsInfected(self._matrix[col][row]) 
     # Spread infection. 
     for x in range(self.cardinalWidth): 
      for y in range(self.cardinalWidth): 
       if self._matrix[x][y] == "infected": 
        self.spread([x,y]) 
#      position = [x,y] 
#      while position: 
#       position = self.spread(position) 

下面的代码无法正常工作，但我没有得到任何错误：

def spread(self, position): 
     for direction in self._directions: 
      (x, y) = self.changePosition(position, direction) 
      if self.canInfectMatrix[x][y] and not self.contactMatrix[x][y]: 
       self.contactMatrix[x][y] = True 
#    self.spread([x,y]) 
       return [x,y] 
      return False 

    def propagate(self): 
     # initialize canInfectMatrix and contactMatrix 
     self.contactMatrix = [[False for row in range(self.cardinalWidth)] for col in range(self.cardinalWidth)] 
     self.canInfectMatrix = [[False for row in range(self.cardinalWidth)] for col in range(self.cardinalWidth)] 
     for col in range(self.cardinalWidth): 
      for row in range(self.cardinalWidth): 
       self.canInfectMatrix[row][col] = self.getsInfected(self._matrix[col][row]) 
     # Spread infection. 
     for x in range(self.cardinalWidth): 
      for y in range(self.cardinalWidth): 
       if self._matrix[x][y] == "infected": 
#     self.spread([x,y]) 
        position = [x,y] 
        while position: 
         position = self.spread(position) 

注意在注释中的变化每种方法的底部

据我所知，这些都应该可以帮助是一样的东西，但他们没有。一个很好，直到我得到递归极限错误。另一个根本不起作用，但我没有发生递归错误。

这些为什么会返回不同的值？

Answer 1

在第二个版本中，您在for循环中使用return语句。这样的返回会中断for循环，当然，这将永远不会恢复。

你想要的是拨打spread()返回一个可能为空的点列表。然后在调用者中将这些新答案附加到待处理点的列表中。调用者可以通过反复从该列表中弹出一个项目进行工作，调用spread()，并将所有新的点添加到列表中 - 并重复，直到列表为空。