outvariable scope и recursion in python

Question

Не могли бы вы рассказать мне, почему отношения parent-child необходимо добавить в цикл 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]] 

EDIT: Вывод этого сценария:

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