Does python lists in recursion do not change to its previous values?

Question

lets say it is my function sparsing a tree through dfs and there is a variable called c for storing the count of nodes and a list call te. my tree is {1:[2,3],2:[1],3:[1]} root is 1. te=[1] c=1 root is 2. te=[1,2] c=2 root is 3 te=[1,2,3] c=2 .my function was dfs(i,te,c) visibly c rolled back but the list did not become [1,3]

def dfs(node,visited,te,c=0):
        if visited[node]==0:
            visited[node]=1
            te.append(node)
            c=c+1
            print(te)
            if node in king:
                for nei in king[node]:
                    if visited[nei]==0:
                        dfs(nei,visited,te,c)

Does this answer your question? [How to clone or copy a list?](https://stackoverflow.com/questions/2612802/how-to-clone-or-copy-a-list) — MisterMiyagi, Jun 22 '20 at 16:31
Also take note that the code *assigns* to ``c`` (thereby *replacing* the old value) whereas it *appends* to ``te`` (thereby *modifying* the same value). — MisterMiyagi, Jun 22 '20 at 16:32
no i dont think it says how to do it in a recursion function. like keeping the list when it rolls back. yes i got your second comment. it makes sense now — Phoenix009, Jun 22 '20 at 16:35
@MisterMiyagi your answer is spot on!! should've given an answer that i could've marked as correct :) — Phoenix009, Jun 22 '20 at 16:43

MisterMiyagi · Accepted Answer · 2020-06-22T16:59:03.037

Values never "change back" to a previous value during recursion. Since integers are immutable, they are assigned a new value (replacing the old) in each recursion step: c=c+1. Since lists are mutable, they can have an element appended to the existing value (modifying the old) in each recursion step: te.append(node).

The simplest change is to create and assign a new value for the list as well:

def dfs(node,visited,te,c=0):
    if visited[node]==0:
        visited[node]=1
        te = te + [node]  # create new list on each recursive step
        c = c + 1
        print(te)
        if node in king:
            for nei in king[node]:
                if visited[nei]==0:
                    dfs(nei, visited, te, c)

Such errors can be avoided by using a tuple instead of a list. A tuple cannot be appended to.

Alternatively, create a copy when passing the list on:

def dfs(node,visited,te,c=0):
    if visited[node]==0:
        visited[node]=1
        te.append(node)
        c = c + 1
        print(te)
        if node in king:
            for nei in king[node]:
                if visited[nei]==0:
                    # copy mutable value before passing it on
                    dfs(nei, visited, te.copy(), c)

Or remove the appended value when done with it:

def dfs(node,visited,te,c=0):
    if visited[node]==0:
        visited[node]=1
        te.append(node)
        c = c + 1
        print(te)
        if node in king:
            for nei in king[node]:
                if visited[nei]==0:
                    dfs(nei, visited, te, c)
        te.pop()  # remove previously appended element

Maybe change back was not the right way to say it was refering to the returning of functions ..how the old value of c was useď after returning. But i get this this c was copies all along. But when i say te i was refering to its address. while working on recursion i keep changing this and that with the hope it works. Sometimes it does. But now i want to find the logic too. Your examples are really giving a clear concept. Thanks for the effort — Phoenix009, Jun 22 '20 at 17:23

score 0 · Answer 2 · answered Jun 22 '20 at 16:27

0

When you pass a list to a function, you're not passing a copy of the list - you're passing a reference to the list. Any change you make to that list in the function will be reflected everywhere else you have referenced that list.

answered Jun 22 '20 at 16:27

Mark Ransom

299,747
42
398
622

yes understandable. Now if i want my list value to rollback then i need to pop the the elements. are there any alternatives? – Phoenix009 Jun 22 '20 at 16:31

score 0 · Answer 3 · answered Jun 22 '20 at 16:33

0

If you add and element to your list, you probably have to remove it once treated with the pop method.

answered Jun 22 '20 at 16:33

Paul Bombarde

311
2
7

Does python lists in recursion do not change to its previous values?

3 Answers3