python: recurcive list processing changes original list

Question

What I'm trying to do is recursively process a list. I'm new to python so when all the code was written and sent to be executed I faced a strange problem: the list returns changed after calling the recursive function. To test this I wrote that:

def recur(n):
    n.append(len(n))
    print '>',n
    if n[-1]<5: recur(n)
    print '<',n

And called the function:

recur([])

Here was the result:

> [0]
> [0, 1]
> [0, 1, 2]
> [0, 1, 2, 3]
> [0, 1, 2, 3, 4]
> [0, 1, 2, 3, 4, 5]
< [0, 1, 2, 3, 4, 5]
< [0, 1, 2, 3, 4, 5]
< [0, 1, 2, 3, 4, 5]
< [0, 1, 2, 3, 4, 5]
< [0, 1, 2, 3, 4, 5]
< [0, 1, 2, 3, 4, 5]

What I expected to see was

> [0]
> [0, 1]
> [0, 1, 2]
> [0, 1, 2, 3]
> [0, 1, 2, 3, 4]
> [0, 1, 2, 3, 4, 5]
< [0, 1, 2, 3, 4, 5]
< [0, 1, 2, 3, 4]
< [0, 1, 2, 3]
< [0, 1, 2]
< [0, 1]
< [0]

, as it is for simple integer variables:

def recur(n):
    n=n+1
    print '>',n
    if n<5: recur(n)
    print '<',n

recur(0)
> 1
> 2
> 3
> 4
> 5
< 5
< 4
< 3
< 2
< 1

How can I fix the situation and what have I understood wrong?

Your question "python: recurcive list processing" is not question. — Phil Frost, Jan 03 '13 at 21:06
@PhilFrost, but "How can I fix the situation and what have I understood wrong?" is a question. — StoryTeller - Unslander Monica, Jan 03 '13 at 21:07
@StoryTeller: I can't tell if you are being sarcastic or not. I'm not saying this is a bad question; I'm saying that the big heading at the top is not phrased as a question. This is important, because when someone is confused about how their list is being mutated, they are not going to search for "recursive list processing". They might search for something like "Why does my list change each time I call a function?" — Phil Frost, Jan 03 '13 at 21:10
@PhilFrost, Your criticism was unclear, and seemed unjust. I don't think a heading must be phrased as a question, but I agree that it should be more closely related to the problem. Hope my edit is an improvement. — StoryTeller - Unslander Monica, Jan 03 '13 at 21:14

score 9 · Accepted Answer · edited May 23 '17 at 10:24

9

All the recursive invocations of your function operate on the same list. You need to make a copy:

def recur(n):
    n.append(len(n))
    print '>',n
    if n[-1]<5: recur(n[:])  # <<<< Note the [:]
    print '<',n

There are some good explanations in the answers to How do I pass a variable by reference?

edited May 23 '17 at 10:24

Community

1
1

answered Jan 03 '13 at 21:03

NPE

486,780
108
951
1,012

score 3 · Answer 2 · answered Jan 03 '13 at 21:08

3

As the other answers indicated, you are mutating the list in place. You could make copies of the list and/or use an immutable data structure, like a tuple:

def recur(n=()):
    if len(n) > 4:
         return n
    return recur(n + (len(n),))

answered Jan 03 '13 at 21:08

Jared

521
4
8

python: recurcive list processing changes original list

2 Answers2