有人能帮忙吗?我想将for循环转换为递归版本

Question

G = [[0, 1, 1, 0, 0], [1, 0, 1, 1, 0], [1, 1, 0, 0, 1], [0, 1, 0, 0, 1], [0, 0, 1, 1, 0]]

def IsDominate(A, S, v):
for i in range(0, len(A)):
vert = S[i]
if (A[vert][v] == 1):
return True
return False
print(IsDominate(G, [0, 3, 2], 1))

基本上，函数将图G的邻接矩阵A、其顶点的子集S和顶点v作为输入。如果S支配v，则函数返回true，否则返回false。

以下是我使用递归的wron代码：

def ISDominate(A, S, v, i):
if i == 0:
return A[0]
vert = S[i]
if (A[vert][v] == 1):
return True
return IsDominate(A,S, v, i-1)
print(ISDominate(G, [0, 2, 3], 1, len(G)-1))

Answer 1

首先，当给定以下邻接图时，您的代码会抛出IndexError：

G = [[0, 0, 0, 0, 0], 
[0, 0, 0, 0, 0], 
[0, 0, 0, 0, 1], 
[0, 0, 0, 0, 1], 
[0, 0, 1, 1, 0]]

这是因为S的长度小于G的长度。当它不能返回True时，它最终会超出索引。

要使代码递归，您可以这样做：

G = [[0, 1, 1, 0, 0], 
[1, 0, 1, 1, 0], 
[1, 1, 0, 0, 1], 
[0, 1, 0, 0, 1], 
[0, 0, 1, 1, 0]]
def IsDominate(A, S, v):
if A[S[0]][v] == 1:
return True
return IsDominate(A,S[1:],v) if S[1:] else False
print(IsDominate(G, [0, 3, 2], 1))

基本上检查第一个条目，并在没有S的第一个条目的情况下递归调用函数。我不建议在这里使用递归，在我看来，这不会增加效率或可读性。