Python 遞迴初學

最近用 python 刷題

刷到要用 DFS 的題目，想用遞迴去寫才發現 python 沒有指標

看著討論的 python 大神寫的程式碼，發現都是 python 裡的參數都是指標

下面拿一題示範 0947 - Most Stones Removed with Same Row or Column

class Solution:
     
     def removeStones(self, stones: List[List[int]]) -> int:
          
          # 想像用 垂直線 跟 水平線 去想辦法連接所有石頭
          # 連接了 n 個, 代表可以去掉 n -1, 看圖
                 
          # 初始樹的數目 以及 複製一個 stones 去做 DFS
          treeNum = 0
          points = {(i, j) for i, j in stones}
          
          # 建立 row 跟 col 兩個 List
          # row 紀錄該 index 下的所有有石頭的 y 座標值
          # col 紀錄該 index 下的所有有石頭的 x 座標值
          row = collections.defaultdict(list)
          col = collections.defaultdict(list)
          for i, j in stones:
               row[i].append(j)
               col[j].append(i)

          for i, j in stones:
               if (i, j) in points:
                    self.dfs(i, j, row, col, points)
                    treeNum += 1

          return len(stones) - treeNum
     
     def dfs(self, x, y, row, col, points):
          
          # 刪除這個點
          points.discard((x, y))

          # 此兩個刪除是為了加速計算
          #row[x].remove(y)
          #col[y].remove(x)

          for i in row[x]:
               if (x, i) in points:
                    self.dfs(x, i, row, col, points)

          for i in col[y]:
               if (i, y) in points:
                    self.dfs(i, y, row, col, points)

以 C 的角度來看 points 不是全域變數根本不可能有用，但在 python 卻成功了
因為在 dfs() 這 function 裡的 points，若沒有特別賦予值的話，就是一個指標指到 call function 所傳入的變數

注意這對 string, int, tuple 無效

參考資料 :  python 新手初學