如何正确写入python 2.7中的递归过程？

Question

我在Python 2.7以下代码：

net = {'Freda': [['Olive', 'John', 'Debra'], ['Starfleet Commander', ' Ninja Hamsters', ' Seahorse Adventures']], 'Ollie': [['Mercedes', 'Freda', 'Bryant'], ['Call of Arms', ' Dwarves and Swords', ' The Movie: The Game']], 'Debra': [['Walter', 'Levi', 'Jennie', 'Robin'], ['Seven Schemers', ' Pirates in Java Island', ' Dwarves and Swords']]} 

def get_secondary_connections(network, person): 
    if person in network: 
     for person in network: 
      connections = network[person][0] 
      result = connections 
      for connection in connections: 
       result = result + get_secondary_connections(network, connection) 
       return result 
    return None   
print get_secondary_connections(net, 'Fred') 

当我执行它提供了以下错误：

result = result + get_secondary_connections(network, connection) 

RuntimeError: maximum recursion depth exceeded 

请告诉我在哪里出了错。

Answer 1

首先，要注意的语义：使用列表[x, y, z]为这你打算通过循环的集合;使用元组(x, y, z)作为你想要索引的固定长度集合，这个集合不够大而不能成为它自己的类。所以，你应该有

net = { 
    'Freda': (['Olive', 'John', 'Debra'], 
       ['Starfleet Commander', ' Ninja Hamsters', ' Seahorse Adventures']), 
    'Ollie': (['Mercedes', 'Freda', 'Bryant'], 
       ['Call of Arms', ' Dwarves and Swords', ' The Movie: The Game']), 
    'Debra': (['Walter', 'Levi', 'Jennie', 'Robin'], 
       ['Seven Schemers', ' Pirates in Java Island', ' Dwarves and Swords']) 
} 

其次，做一个递归问题时，通过你想先用一些例子来发生的，因为如果你的机器是什么步骤。处理Freda时，您的第一项任务是加载她的连接Olive, John, Debra。你想用这些做什么？那么你要尝试加载橄榄的连接出现故障，试图加载约翰的连接出现故障，然后尝试加载黛布拉的连接，那么你就必须Walter, Levi, Jennie, Robin.什么你想在这个名单呢？把它返还？与其他人的朋友串连起来？关于次级连接没有任何“递归”，至少不像人们通常认为的那样。换句话说，它似乎与要定义的函数的名称相匹配：

def get_secondary_connections(network, person): 
    primary_connections, movies = network.get(person, ([], [])) 
    out = [] 
    for friend in primary_connections: 
     secondary_connections, movies = network.get(person, ([], [])) 
     out.extend(secondary_connections) 
    return out 

无需递归。我们什么时候需要递归？那么，如果我们想找到大家谁这个人是由朋友或朋友-的-A-朋友或连接到一个朋友-的-A-朋友-的-A-朋友，然后我们需要探索整个图和递归可能会有所帮助。当然，我们可能也希望这个东西不要包含重复项，所以我们可能需要使用set而不是list。

的首种尝试可能是：

def get_all_connections(network, person): 
    primary_connections, movies = network.get(person, ([], [])) 
    out = set(primary_connections) # copy this list into an output set 
    for friend in primary_connections: 
     out = out.union(get_all_connections(network, person)) 
    return out 

而且现在你会发现，的确，在排序网络的错，这件事情很容易超过最大递归深度。这是一个简单的网络：

net = { 
    'Alice': (['Bob'], []), 
    'Bob': (['Alice'], []) 
} 

为什么会发生这种情况？因为找到Alice的所有朋友，你需要找到Bob的所有朋友，但要找到Bob的所有朋友，你需要找到Alice的所有朋友。那么我们如何克服这一点？

我们可以要求所有鲍勃的朋友不包括那些通过爱丽丝来。这将需要一个完整的清单，否则我们只会绊倒其他循环的情况下，如：

net = { 
    'Alice': (['Bob'], []), 
    'Bob': (['Carol', 'Dylan'], []), 
    'Carol': (['Alice'], []), 
    'Dylan': (['Bob'], []) 
} 

注意，当我们问Bob的朋友，我们将递归两个卡罗尔和迪伦，我们需要告诉既他们排除都爱丽丝和鲍勃，因为已经被处理。因此，导致

def get_all_connections(network, person, excluding=()): 
    if person in excluding: 
     return set() # we exclude by immediately returning the empty set. 
    excluding_us_too = excluding + (person,) 
    primary_connections, movies = network.get(person, ([], [])) 
    out = set(primary_connections) 
    for friend in primary_connections: 
     out = out.union(get_all_connections(network, person, excluding_us_too)) 
    return out 

这个周期检测策略是由几个不同的名称，但通常这里的元组被称为“路径”，因为当我们处理任何的迪伦的朋友也说('Dylan', 'Bob', 'Alice')，这意味着我们通过先访问爱丽丝，然后是鲍勃，然后是迪伦来到迪伦的朋友那里。

请注意，'卡罗尔'在迪伦的路上无处可寻;有时这可能是一件好事，有时候不会：如果Dylan连接到Carol并且应用到Carol的get_all_connections即使在排除Alice和Bob和Dylan的情况下也会产生一百万个结果，那么我们可以预期这两个结果都会为Dylan产生相同的结果，然后当我们到达Bob时，我们必须将这两百万个结果编成union，这些结果只有一百万 - 这是很多不必要的工作！

因此，另一个刺将是保持人员处理队列和我们处理的人员。在这一点上你不会想要使用递归，你更愿意使用正常的循环结构。

def get_all_connections(network, person): 
    visited, to_visit, out = set(), set([person]), set() 
    while len(to_visit) > 0: 
     visiting = to_visit.pop() 
     visited.add(visiting) 
     connections, movies = network.get(visiting, ([], [])) 
     for friend in connections: 
      out.add(friend) 
      if friend not in visited: 
       to_visit.add(friend) 
    return out 

像这样的循环可以被转换成一个高效的递归，但不幸的是Python不使这种风格递归的效率，使运动的学术，而不是实际的。