CODEWITHSUNDEEP
pythonlistrecursionappend
thegib50
thegib50

Reputation: 13

python recursion appending to list

I am trying to to append current to master every time current changes. I have been unsuccessful using list. I have been able to to modify strings and append different strings to master but it would be much easier if I could use list.

master = []

def recur(count,current):
    count = count + 1
    if (count == 5):
        return
    current.append(1)
    master.append(current)
    recur(count,current)


recur(0,[])

print(master)
# out put
# [[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]

# what I expected
# [[1], [1,1], [1,1,1], [1,1,1,1]]

Upvotes: 1

Views: 1038

Answers (3)

Ch3steR
Ch3steR

Reputation: 20669

The reason is you are appending the reference of the current list to master. So, every time you change current the previously appended lists also change.

Use this link for visualization:click here

enter image description here

>>>def recur(count,current):
    count = count + 1
    if (count == 5):
        return
    current.append(1)
    master.append(current)
    recur(count,current)


>>> master=[]
>>> recur(0,[])
>>> master
[[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]
>>> for i in master:
    id(i)


2485591104264
2485591104264
2485591104264
2485591104264
>>>

Method 1

You can try this. There is no need to keep track of the current list you are appending to master. 

def recur(count):
    count+=1
    if count==5:
        return
    curr=[1]*count
    #print(curr)
    master.append(curr)
    recur(count)
master=[]
recur(0)
print(master)

[[1], [1, 1], [1, 1, 1], [1, 1, 1, 1]]

Method 2

If you are keen on using current then try this. Visualization for this code click here.

Image 2

def recur(count,curr):
    count+=1
    if count==5:
        return
    curr.append(1)
    master.append(curr)
    recur(count,curr[:])
master=[]
recur(0,[])
print(master)

[[1], [1, 1], [1, 1, 1], [1, 1, 1, 1]]

Method 3

Or you can try this.

def recur(count,curr):
    count+=1
    if count==5:
        return
    curr.append(1)
    master.append(curr[:])
    recur(count,curr)
master=[]
recur(0,[])
print(master)

[[1], [1, 1], [1, 1, 1], [1, 1, 1, 1]]

Method 4

If you want to return [[1], [1, 1], [1, 1, 1], [1, 1, 1, 1]] then try this.

def recur(count,curr):
    count+=1
    if count==5:
        return []
    curr.append(1)
    return [curr]+recur(count,curr[:])
master=recur(0,[])
print(master)
another_master=recur(0,[])
print(another_master)

[[1], [1, 1], [1, 1, 1], [1, 1, 1, 1]]

[[1], [1, 1], [1, 1, 1], [1, 1, 1, 1]]

Upvotes: 1

Shibiraj
Shibiraj

Reputation: 769

Try the code below,

master = []

def recur(count, current):
    count += 1
    if (count == 5):
        return
    tmp = current[:]
    tmp.append(1)
    master.append(tmp)
    recur(count, tmp)

recur(0, [])

master

output

[[1], [1, 1], [1, 1, 1], [1, 1, 1, 1]]

Upvotes: 0

James McCorrie
James McCorrie

Reputation: 2652

This is what you want:

master = []

def recur(count, current):
    count += 1
    if (count == 5):
        return

    new_current = current.copy()

    new_current.append(1)
    master.append(new_current)

    recur(count, new_current)


recur(0, [])

print(master)

The issue is that current is a reference to the list object... not the actual list itself. So when you append current to master you are just appending a reference to the same list object. So when you add a new element to the current list it's added to the one list that all of your references are pointing to.

The solution is to take a copy of current list to store its state at that time. There are different types of copy - deep and shallow. Shallow would make a copy of the list object but not it's elements, a deep copy will recurse through the elements and any subelements if you have a list of lists for example.

Upvotes: 2

Related Questions