CODEWITHSUNDEEP
pythonrecursion
Cooper.Wu
Cooper.Wu

Reputation: 4565

What's the best way of appending in a recursive method in Python?

In below code, I am trying to parse a string '1/2/3/4/5/6/' to a hierarchy tree, expect output should like this:

# 1 -> 2 
# 2 -> 3
# 3 -> 4
# 4 -> 5
# 5 -> 6

but it returns:

# 1 -> [2, 3, 4, 5, 6]

After I print some variables, I found the reason, variable 'a1' not only for the first 'a1', but also stand for all variables named 'a1', every call method, it produce a 'a1' variable, and operate on it. Python doesn't like other OO language, 'a1' expected to be the only variable in currently call only. So my question is, what's the best way to solve this kind of problem in Python?

class A(object):
    name = ''
    children = []

    def __repr__(self):
        return '%s -> %s' % (self.name, self.children)

def recurse(a1, s):
    if len(s) == 0: return

    s1 = s[0:s.find('/')]
    a1.name = s1
    print 's1: %s' % (s1)

    s2 = s[s.find('/') + 1:]
    print 's2: %s' % (s2)

    a2 = A()
    a1.children.append(a2) # Problem: why all child append into variable 'a' and all children too?
    # print 'locals() -> ', locals()    when I print locals(), I got the reason, but what's the best way to fix the problem?
    recurse(a2, s2)

a = A()
recurse(a, '1/2/3/4/5/6/') # input string required to ends with '/'

# expect: 
# 1 -> 2 
# 2 -> 3
# 3 -> 4
# 4 -> 5
# 5 -> 6

print a

Upvotes: 1

Views: 93

Answers (2)

perreal
perreal

Reputation: 97948

Since you are adding each node as a child to the previous node, you obtain a chain relationship. You can make the function return a list of nodes instead:

class A(object):
    def __init__(self,name):
        self.name = name
        self.children = []
    def __repr__(self):
        return '%s -> %s' % (self.name, self.children)

def recurse(s,l=[]):
    v = s.split("/")
    if len(v) < 3: return
    a1,a2 = A(v[0]), A(v[1])
    a1.children.append(a2)
    v.pop(0)
    l.append(a1)
    recurse("/".join(v),l)
    return l

for i in recurse('1/2/3/4/5/6/'):
    print i

Output:

1 -> [2 -> []]
2 -> [3 -> []]
3 -> [4 -> []]
4 -> [5 -> []]
5 -> [6 -> []]

Upvotes: 1

John La Rooy
John La Rooy

Reputation: 304167

Your children is a class attribute, so all the instances will be sharing and modifying the same list

class A(object): 
    name = ''                      # these are class
    children = []                  # attributes

You should give each instance it's own list

class A(object):
    def __init__(self):
        self.name = ''             # these are instance
        self.children = []         # attributes

Upvotes: 4

Related Questions