在递归函数参数中修改列表时会发生什么
What happens to list when it is modified in recursive function arguments
这是n皇后问题的解法。在递归调用中,它传递修改后的列表。我的问题是对于每个递归调用,它是否创建三个新列表:queens、xy_dif、xy_sum 并将它们保存在调用堆栈中?或者只有这三个列表,每个递归调用只是修改它们?如果是这样的话,我不明白它是如何解决如下问题的:
DFS([],[],[]) 调用 DFS([0], [0], [0]),然后 DFS([0], [0], [0]) 调用 DFS( [0,2],[0,-1],[0,3]), 它没有通过 if 条件所以它 returns.
然后for循环继续,q=3,我的问题是为什么下一次调用是DFS([0,3],[0,-2],[0,4])而不是DFS([0 ,2,3],[0,-1,-2],[0,3,4])?
这三个列表在调用 DFS([0], [0], [0]) 后如何恢复到原始状态?
def solveNQueens(self, n):
def DFS(queens, xy_dif, xy_sum):
print('call function DFS({},{},{})'.format(queens, xy_dif, xy_sum))
p = len(queens)
print('updated row p is ', p)
if p==n:
result.append(queens)
print('p==n, result is ', result)
return None
for q in range(n):
print('loop starts, q is ', q)
if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])
result = []
DFS([],[],[])
return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]
添加一些"standard"递归跟踪,您可以很容易地看到结果。在这种情况下,id
函数是您的朋友,显示特定参数是否指代同一实体。
正如您在下面的输出中看到的,每个参数都有一个唯一的 ID:它是一个独立的对象。这是因为您 没有 将一个调用的参数传递给下一个调用。相反,您已经在堆栈上创建了一个临时变量。例如,如果您只是通过 queens
,那么该列表引用将由所有调用共享。
另一方面,queens+[q]
是不是queens
;相反,它是一个新的列表表达式:堆栈上的一个临时变量,具有单独的值。
如果您希望共享结构,您将首先更改 queens
,然后将更改后的版本传递到下一个级别:
queens.append(q)
DFS(queens, xy_dif+[p-q], xy_sum+[p+q])
在这种用法中,xy_diff
和 xy_sum
在每次调用时仍然是独立变量,但 queens
是共享的。
你的递归检测代码:
indent = ""
def DFS(queens, xy_dif, xy_sum):
global indent
print(indent, "ENTER DFS", queens, xy_dif, xy_sum)
print(indent, "parameter IDs:", id(queens), id(xy_dif), id(xy_sum))
indent += " "
print('call function DFS({},{},{})'.format(queens, xy_dif, xy_sum))
p = len(queens)
print('updated row p is ', p)
if p==n:
result.append(queens)
print('p==n, result is ', result)
indent = indent[2:]
return None
for q in range(n):
print('loop starts, q is ', q)
if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])
result = []
DFS([],[],[])
send_back = [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]
print(indent, "LEAVE DFS", queens, xy_dif, xy_sum)
indent = indent[2:]
return send_back
输出开始:
ENTER DFS [] [] []
parameter IDs: 1813255818376 1813255818888 1813255819016
call function DFS([],[],[])
updated row p is 0
loop starts, q is 0
ENTER DFS [0] [0] [0]
parameter IDs: 1813255827784 1813258276680 1813255818760
call function DFS([0],[0],[0])
updated row p is 1
loop starts, q is 0
loop starts, q is 1
loop starts, q is 2
ENTER DFS [0, 2] [0, -1] [0, 3]
parameter IDs: 1813255817480 1813255817352 1813255817928
call function DFS([0, 2],[0, -1],[0, 3])
updated row p is 2
loop starts, q is 0
loop starts, q is 1
loop starts, q is 2
loop starts, q is 3
ENTER DFS [] [] []
parameter IDs: 1813255817864 1813255817736 1813255816712
call function DFS([],[],[])
updated row p is 0
loop starts, q is 0
ENTER DFS [0] [0] [0]
parameter IDs: 1813255816392 1813255816264 1813255816136
call function DFS([0],[0],[0])
...
这是n皇后问题的解法。在递归调用中,它传递修改后的列表。我的问题是对于每个递归调用,它是否创建三个新列表:queens、xy_dif、xy_sum 并将它们保存在调用堆栈中?或者只有这三个列表,每个递归调用只是修改它们?如果是这样的话,我不明白它是如何解决如下问题的:
DFS([],[],[]) 调用 DFS([0], [0], [0]),然后 DFS([0], [0], [0]) 调用 DFS( [0,2],[0,-1],[0,3]), 它没有通过 if 条件所以它 returns.
然后for循环继续,q=3,我的问题是为什么下一次调用是DFS([0,3],[0,-2],[0,4])而不是DFS([0 ,2,3],[0,-1,-2],[0,3,4])?
这三个列表在调用 DFS([0], [0], [0]) 后如何恢复到原始状态?
def solveNQueens(self, n):
def DFS(queens, xy_dif, xy_sum):
print('call function DFS({},{},{})'.format(queens, xy_dif, xy_sum))
p = len(queens)
print('updated row p is ', p)
if p==n:
result.append(queens)
print('p==n, result is ', result)
return None
for q in range(n):
print('loop starts, q is ', q)
if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])
result = []
DFS([],[],[])
return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]
添加一些"standard"递归跟踪,您可以很容易地看到结果。在这种情况下,id
函数是您的朋友,显示特定参数是否指代同一实体。
正如您在下面的输出中看到的,每个参数都有一个唯一的 ID:它是一个独立的对象。这是因为您 没有 将一个调用的参数传递给下一个调用。相反,您已经在堆栈上创建了一个临时变量。例如,如果您只是通过 queens
,那么该列表引用将由所有调用共享。
另一方面,queens+[q]
是不是queens
;相反,它是一个新的列表表达式:堆栈上的一个临时变量,具有单独的值。
如果您希望共享结构,您将首先更改 queens
,然后将更改后的版本传递到下一个级别:
queens.append(q)
DFS(queens, xy_dif+[p-q], xy_sum+[p+q])
在这种用法中,xy_diff
和 xy_sum
在每次调用时仍然是独立变量,但 queens
是共享的。
你的递归检测代码:
indent = ""
def DFS(queens, xy_dif, xy_sum):
global indent
print(indent, "ENTER DFS", queens, xy_dif, xy_sum)
print(indent, "parameter IDs:", id(queens), id(xy_dif), id(xy_sum))
indent += " "
print('call function DFS({},{},{})'.format(queens, xy_dif, xy_sum))
p = len(queens)
print('updated row p is ', p)
if p==n:
result.append(queens)
print('p==n, result is ', result)
indent = indent[2:]
return None
for q in range(n):
print('loop starts, q is ', q)
if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])
result = []
DFS([],[],[])
send_back = [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]
print(indent, "LEAVE DFS", queens, xy_dif, xy_sum)
indent = indent[2:]
return send_back
输出开始:
ENTER DFS [] [] []
parameter IDs: 1813255818376 1813255818888 1813255819016
call function DFS([],[],[])
updated row p is 0
loop starts, q is 0
ENTER DFS [0] [0] [0]
parameter IDs: 1813255827784 1813258276680 1813255818760
call function DFS([0],[0],[0])
updated row p is 1
loop starts, q is 0
loop starts, q is 1
loop starts, q is 2
ENTER DFS [0, 2] [0, -1] [0, 3]
parameter IDs: 1813255817480 1813255817352 1813255817928
call function DFS([0, 2],[0, -1],[0, 3])
updated row p is 2
loop starts, q is 0
loop starts, q is 1
loop starts, q is 2
loop starts, q is 3
ENTER DFS [] [] []
parameter IDs: 1813255817864 1813255817736 1813255816712
call function DFS([],[],[])
updated row p is 0
loop starts, q is 0
ENTER DFS [0] [0] [0]
parameter IDs: 1813255816392 1813255816264 1813255816136
call function DFS([0],[0],[0])
...