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?

Answer 1

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?

Answer 2

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),))