I am using a recursive function implemented in a python class. Am I right that the local variable (passed through the methods attributes) isn't changing through a recursive change?
I have the following tree: example tree
My current method is the following:
def readSequence(self, linkTable, partTable, seq, element):
#clearFlags returns an array of objects with flags set to 0
partTable = self.clearFlags(partTable)
#readFlags returns an array of objects with updated flags. (flag > 0 if object is in sequence)
partTable = self.readFlags(partTable, seq)
#readChildren returns an array of objects with all children of the current element
children = self.readChildren(linkTable, partTable, element)
if len(children) == 0:
self.subsequences.append(seq)
else:
for child in children:
if child.flag == 1:
self.subsequences.append(seq)
return
else:
seq.append(child)
self.readSequence(linkTable, partTable, seq, child)
In my understanding the sequence seq should grow as follows:
[1]
[1, 2]
[1, 2, 4]
--> appended to subsequences[1, 2, 5]
--> appended to subsequences[1, 3]
--> appended to subsequences
But instead it does this:
[1]
[1, 2]
[1, 2, 4]
--> appended to subsequences[1, 2, 4, 5]
--> appended to subsequences[1, 2, 4, 5, 3]
--> appended to subsequences
The problem is clearly that the sequence seq is changed like a global variable and doesn't stay the same to add the other child.
Hope you can help me! Thanks in advance!
CodePudding user response:
list
is a mutable type in python.
Essentially, that means that lists are passed by reference rather than by value; if two variables refer to the same list, then modifying one will reflect on the other.
For instance:
seq = [1,2,3]
b = seq
b.append(4)
print(seq) # [1,2,3,4]
Likewise if you pass seq
to a function, and the function modifies it, then seq
is really modified, not just a copy:
def f(l):
l.append(4)
seq = [1,2,3]
f(l)
print(seq) # [1,2,3,4]
If you don't want this behaviour, then there are three possible solutions:
- Use a non-mutable type, such as a
tuple
, instead of alist
; or - explicitly make a copy, using
list(seq)
orseq.copy()
; or - undo the changes before you return from the recursive call.
Use a non-mutable type or explicitly make a copy
For instance:
# USING A NON-MUTABLE TYPE
def f(l):
l = (*l, 4)
seq = (1,2,3) # tuple
f(seq)
print(seq) # (1,2,3)
# MAKING A COPY
def f(l):
l.append(4)
seq = [1,2,3]
f(list(seq)) # explicitly pass a copy rather than the original
print(seq) # [1,2,3]
Undo the changes before returning from the recursive call
The two options above would add to the complexity of your function, because making a copy at every recursive call takes time linear in the length of the list at every recursive call.
Instead, you can undo your list.append
by following it with a list.pop
.
Replace:
seq.append(child)
self.readSequence(linkTable, partTable, seq, child)
with:
seq.append(child)
self.readSequence(linkTable, partTable, seq, child)
seq.pop()