list parameter of a recursive function

[Chris Torek]

In article <rsuun7-eml.ln1 at rama.universe>
TP  <Tribulations at Paralleles.invalid> wrote:
>I have a function f that calls itself recursively. It has a list as second 
>argument, with default argument equal to None (and not [], as indicated at:
>http://www.ferg.org/projects/python_gotchas.html#contents_item_6 )
>
>This is the outline of my function:
>
>def f ( argument, some_list = None ):
>
>   if some_list == None:
>      some_list = []
>   [...]
>   # creation of a new_argument
>   # the function is called recursively only if some condition is respected
>   if some_condition:
>      some_list.append( elem )
>      f( new_argument, some_list )
>   # otherwise, we have reached a leaf of the a branch of the recursive tree
>   # (said differently, terminal condition has been reached for this branch)
>   print "Terminal condition"
>
>The problem is that when the terminal condition is reached, we return back 
>to some other branch of the recursive tree, but some_list has the value 
>obtained in the previous branch!

Yes, this is the way it is supposed to work. :-)

>So, it seems that there is only one some_list list for all the recursive 
>tree.  To get rid of this behavior, I have been compelled to do at the
>beginning of f:
>
>import copy from copy

[from copy import copy, rather]

>some_list = copy( some_list )
>
>I suppose this is not a surprise to you: I am compelled to create a new 
>some_list with the same content.

The above will work, or for this specific case, you can write:

    some_list = list(some_list)

which has the effect of making a shallow copy of an existing list:

   >>> base = [1, 2]
   >>> l1 = base
   >>> l2 = list(l1)
   >>> l1 is l2
   False
   >>> l1[0] is l2[0]
   True
   >>> base.append(3)
   >>> l2
   [[1, 2, 3]]
   >>>

but will also turn *any* iterator into a (new) list; the latter
may often be desirable.

>So, if I am right, all is happening as if the parameters of a function are 
>always passed by address to the function. Whereas in C, they are always 
>passed by copy (which gives relevance to pointers).
>
>Am I right?

Mostly.  Python distinguishes between mutable and immutable items.
Mutable items are always mutable, immutable items are never mutable,
and the mutability of arguments is attached to their "fundamental
mutability" rather than to their being passed as arguments.  This
is largely a point-of-view issue (although it matters a lot to
people writing compilers, for instance).

Note that if f() is *supposed* to be able to modify its second
parameter under some conditions, you would want to make the copy
not at the top of f() but rather further in, and in this case,
that would be trivial:

        def f(arg, some_list = None):
            if some_list is None:
                some_list = []
            ...
            if some_condition:
                # make copy of list and append something
                f(new_arg, some_list + [elem])
            elif other_condition:
                # continue modifying same list
                f(new_arg, some_list)
            ...

(Note: you can use also the fact that list1 + list2 produces a new
list to make a copy by writing "x = x + []", or "x = [] + x", but
"x = list(x)" is generally a better idea here.)
-- 
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W)  +1 801 277 2603
email: gmail (figure it out)      http://web.torek.net/torek/index.html