跟踪递归函数在 Python 中被调用了多少次

Question

我有一段 Python 代码实现了递归回溯算法，用于解决国际象棋中著名的 N 皇后问题。

def Backtrack(board, col):

  if col >= N:
    return True

  for i in range(N):
      if (ld[i - col + N - 1] != 1 and rd[i + col] != 1) and cl[i] != 1:
          board[i][col] = 1
          ld[i - col + N - 1] = rd[i + col] = cl[i] = 1
          if Backtrack(board, col + 1):
              return True
          board[i][col] = 0 # Backtrack 
          ld[i - col + N - 1] = rd[i + col] = cl[i] = 0

  return False

哪里

ld = np.zeros(2*N - 1, dtype=int)
rd = np.zeros(2*N - 1, dtype=int)
cl = np.zeros(N, dtype=int)
board = np.zeros((N, N), dtype=int)

问题：

我想跟踪递归回溯算法被调用了多少次。

我的尝试：

我在代码中添加了一个计数器变量，这样

def Backtrack(board, col, counter):

  counter += 1
  print('here', counter)

  if col >= N:
    return True

  for i in range(N):
      if (ld[i - col + N - 1] != 1 and rd[i + col] != 1) and cl[i] != 1:
          board[i][col] = 1
          ld[i - col + N - 1] = rd[i + col] = cl[i] = 1
          if Backtrack(board, col + 1, counter):
              return True
          board[i][col] = 0 # Backtrack 
          ld[i - col + N - 1] = rd[i + col] = cl[i] = 0

  return False

然而对于 N = 4 输出是

here 1
here 2
here 3
here 3
here 4
here 2
here 3
here 4
here 5

这表明我的尝试是错误的。该函数被调用了 9 次，但最后计数器变量为 5。

Answer 1

整数是不可变的，因此当您执行 counter += 1 时，您创建了一个新数字，比如从 1 到 2，并且 2 现在已绑定到名称 counter。因此，当您处于深度 2 并调用该函数两次时，两次调用都会将 2 递增到它们自己的 3。在 python 中，您不是按变量传递，而是按名称传递，因此 counter 不是'在所有通话中都指的是同一件事。

您想要的是可变变量或全局变量。例如

# or a class implementation equivalent
counter = 0
def backtrack(board, col):
    global counter
    counter += 1
    # the rest

但这样一来，您每次想要重新启动算法时都需要将 counter 重置为 0。因此，我认为最好做

def backtrack(board, col, counter=None):
    if not counter:
        counter = [0]
    counter[0] += 1
    # the rest of your function

做 backtrack(board, col, counter=[0]) 时要非常小心，因为 counter 会变成 initialised to the list only once。解决后，例如 N=4，它将具有值 9，如果您再次调用该函数，它将从那里继续递增。

Answer 2

肮脏的技巧： 使用 Python 中的默认参数在函数调用之间共享的事实：

def Backtrack(board, col, counter = [0]):

  counter[0]+=1
  print('here', counter[0])

正确解法： 在 class:

中包含您的方法

class Board():
    counter = 0

    def Backtrack(self, board, col):

        self.counter+=1
        print('here', self.counter)

后来这样称呼：

Board().Backtrack(board, 0)

跟踪递归函数在 Python 中被调用了多少次

Keep track of how many times a recursive function has been called in Python

python

recursion

numpy

backtracking

n-queens

问题：

我的尝试：