python中的外变量作用域和递归

Question

请告诉我为什么父-子关系需要追加到for循环中以获得预期的输出。我不理解Python中的范围。

#a unique id to be given to each node
current_id = 0
#ids = [parent_id, current_id]; stores parent_child tree data
ids = []
#MWE of depth first search
def bt(parent_id):
   global ids
   global current_id
   #increament current id because we just created a new node
   current_id = current_id +1
   #store the parent to child relationship in the list called ids
   ids.append([parent_id,current_id]) 
   #show the parent child relationship that is getting append to the ids list
   print 'parent-child (outside loop)', [parent_id,current_id]
   if(parent_id) > 1:
       return
   for i in range(2):
        print 'parent-child (inside loop)', [parent_id,current_id]
        bt(current_id)
#run depth first search
print bt(0)
#print list of parent to child relationships
print 'list of parent-child relationships\n',ids
print 'expected output',[[0,1],[1,2],[1,3],[0,4]]

编辑:此脚本的输出如下：

parent-child (outside loop) [0, 1]
parent-child (inside loop) [0, 1]
parent-child (outside loop) [1, 2]
parent-child (inside loop) [1, 2]
parent-child (outside loop) [2, 3]
parent-child (inside loop) [1, 3]
parent-child (outside loop) [3, 4]
parent-child (inside loop) [0, 4]
parent-child (outside loop) [4, 5]
None
list of parent-child relationships
[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]]
expected output [[0, 1], [1, 2], [1, 3], [0, 4]]

Answer 1

我认为，您遇到的问题是使用current_id的全局变量。当您在递归调用中创建子调用时，current_id也会为父调用更新。

下面是一个简单的例子：

 x = 0
 def foo(level=0):
     global x
     print(" "*level+str(x))
     x += 1
     if level < 3:
         foo(level+1)
     print(" "*level+str(x))
 foo()

这将打印：

 0
  1
   2
    3
    4
   4
  4
 4

由于使用了level参数，缩进表示递归的级别。每次递归调用都会增加x的值，但是当调用解除时它不会下降。这是因为它是一个全局变量，因此内部递归级别所做的更改由外部级别看到。

在代码中，可以通过在局部变量中保留对原始current_id值的引用来修复此问题：

def bt(parent_id):
   global current_id
   current_id = current_id +1
   ids.append([parent_id,current_id])

   my_id = current_id # make a local reference to the current_id

   print('parent-child (outside loop)', [parent_id,my_id])
   if(parent_id) > 1:
       return
   for i in range(2):
        print('parent-child (inside loop)', [parent_id,my_id])
        bt(my_id) # use the local reference for the recursion

输出仍然不完全符合您的预期，但这是有意义的：

parent-child (outside loop) [0, 1]
parent-child (inside loop) [0, 1]
parent-child (outside loop) [1, 2]
parent-child (inside loop) [1, 2]
parent-child (outside loop) [2, 3]
parent-child (inside loop) [1, 2]
parent-child (outside loop) [2, 4]
parent-child (inside loop) [0, 1]
parent-child (outside loop) [1, 5]
parent-child (inside loop) [1, 5]
parent-child (outside loop) [5, 6]
parent-child (inside loop) [1, 5]
parent-child (outside loop) [5, 7]
None
list of parent-child relationships
[[0, 1], [1, 2], [2, 3], [2, 4], [1, 5], [5, 6], [5, 7]]
expected output [[0, 1], [1, 2], [1, 3], [0, 4]]

如果要绘制一个图表，显示您在ids中构建的树型组织，您将得到：

    (0)  # This is not a real element, but the root's "parent"
     |
     1
    / \
   /   \
  2     5
 / \   / \
3   4 6   7