回傳遞回函式與回傳存盤遞回函式值的變數

這兩個函式回傳不同的結果。他們看起來和我一模一樣。這里發生了什么？

def DFS(r, c, grid):
   if (r<0 or r>=len(grid) or c<0 or c>=len(grid[0])):
      return False
   if (grid[r][c] == 1):
      return True
      
      grid[r][c]=1
      return DFS(r 1, c, grid) and DFS(r-1, c, grid) and DFS(r, c 1, grid) and DFS(r, c-1, grid)

和

def DFS(r, c, grid):
   if (r<0 or r>=len(grid) or c<0 or c>=len(grid[0])):
      return False
   if (grid[r][c] == 1):
      return True
   grid[r][c] = 1

   down = DFS(r 1, c, grid)
   up = DFS(r-1, c, grid)
   right = DFS(r, c 1, grid)
   left = DFS(r, c-1, grid)
   return down and up and right and left

例如在這個代碼塊中，

for r in range(len(grid)):
            for c in range(len(grid[0])):
                if (grid[r][c] == 0):
                    #print("searching", r, c)
                    if (DFS(r, c, grid) == True):
                        print([r,c])
                        result =1
        return result

給定此輸入時，兩個 DFS 函式將回傳不同的值：

[[0,0,1,1,0,1,0,0,1,0],[1,1,0,1,1,0,1,1,1,0],[1,0,1,1,1,0,0,1,1,0],[0,1,1,0,0,0,0,1,0,1],[0,0,0,0,0,0,1,1,1,0],[0,1,0,1,0,1,0,1,1,1],[1,0,1,0,1,1,0,0,0,1],[1,1,1,1,1,1,0,0,0,0],[1,1,1,0,0,1,0,1,0,1],[1,1,1,0,1,1,0,1,1,0]]

謝謝您的幫助！

uj5u.com熱心網友回復：

第一個版本使用短路評估來評估對 DFS 的最后 4 次呼叫：即，如果 return 陳述句中的第一個 DFS 呼叫回傳錯誤值，則and操作員甚至不會費心評估接下來的 3 次 DFS 呼叫。

最后一個版本首先明確評估所有 4 個 DFS 呼叫，然后才評估 4-way and。

我猜這會對grid[r][c] = 1執行該行的頻率和時間產生影響，這可以解釋為什么它們的行為不同。

uj5u.com熱心網友回復：

在另一個答案中有一個宣告：

我猜這會對grid[r][c]=1執行該行的頻率和時間產生影響，這可以解釋為什么它們的行為不同。

這個猜測是正確的，下面的代碼證明了第二個函式等同于第一個函式。assert result_1 == result_2not raise an assertion 錯誤表明這兩個函式現在以相同的方式作業：

# These two functions are returning different results. 
# They look identical to me. What is going on here?
def DFS1(r, c, grid):
   if (r<0 or r>=len(grid) or c<0 or c>=len(grid[0])):
      return False
   if (grid[r][c] == 1):
      return True
      
   grid[r][c]=1

   return DFS1(r 1, c, grid) and DFS1(r-1, c, grid) and DFS1(r, c 1, grid) and DFS1(r, c-1, grid)
# The functions in your question were not equivalent. 
# The equivalent function to this above will be: 
def DFS2(r, c, grid):
    if (r<0 or r>=len(grid) or c<0 or c>=len(grid[0])):
       return False
    if (grid[r][c] == 1):
       return True

    grid[r][c] = 1

    if down:= DFS2(r 1, c, grid):
        if up:= DFS2(r-1, c, grid):
            if right:= DFS2(r, c 1, grid):
                if left:= DFS2(r, c-1, grid):
                    return True                    
                      # ^-- as (down and up and right and left) == True
    return False    
    #   ^-- as (down and up and right and left) == False
# For example in this code block,
result_1 = 0
grid = [[0,0,1,1,0,1,0,0,1,0],[1,1,0,1,1,0,1,1,1,0],[1,0,1,1,1,0,0,1,1,0],[0,1,1,0,0,0,0,1,0,1],[0,0,0,0,0,0,1,1,1,0],[0,1,0,1,0,1,0,1,1,1],[1,0,1,0,1,1,0,0,0,1],[1,1,1,1,1,1,0,0,0,0],[1,1,1,0,0,1,0,1,0,1],[1,1,1,0,1,1,0,1,1,0]]
for r in range(len(grid)):
    for c in range(len(grid[0])):
        if (grid[r][c] == 0):
            #print("searching", r, c)
            if (DFS1(r, c, grid) == True):
                print([r,c])
                result_1 =1

result_2 = 0
print(' --- ' )
grid = [[0,0,1,1,0,1,0,0,1,0],[1,1,0,1,1,0,1,1,1,0],[1,0,1,1,1,0,0,1,1,0],[0,1,1,0,0,0,0,1,0,1],[0,0,0,0,0,0,1,1,1,0],[0,1,0,1,0,1,0,1,1,1],[1,0,1,0,1,1,0,0,0,1],[1,1,1,1,1,1,0,0,0,0],[1,1,1,0,0,1,0,1,0,1],[1,1,1,0,1,1,0,1,1,0]]
for r in range(len(grid)):
    for c in range(len(grid[0])):
        if (grid[r][c] == 0):
            #print("searching", r, c)
            if (DFS2(r, c, grid) == True):
                print([r,c])
                result_2 =1

# These two DFS functions above will return the same values. 
assert result_1 == result_2

標籤：Python 递归

上一篇：為什么在這種情況下使用引數語法運算子“[”？AsLike""['i']""我用作RGSS、RPGMakerXP和win32api和ruby?

下一篇：在OCaml中遞回洗掉重復的尾部