list parameter of a recursive function
Diez B. Roggisch
deets at web.de
Thu Oct 7 00:29:09 CEST 2010
TP <Tribulations at Paralleles.invalid> writes:
> 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!
> So, it seems that there is only one some_list list for all the recursive
> To get rid of this behavior, I have been compelled to do at the beginning of
> import copy from copy
> 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.
> 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?
Yes and no. For some sensible definition of yes (this is to avoid the
*endless* discussions about python parameter passing semantics and it's
relation to common, yet misunderstood or unprecisely defined definitions
of parameter passing), passing around a mutable object (such as a list
or dictionary) will be like a pointer - mutations are visible to all
others having a reference to it.
You are wrong though that C-semantics are different, meaning that
"passing by copy" is not what happens. Some things are copied (primitive
types, structs that are passed directly). But not, for example - and
relevant to this case - arrays (as they are "only" pointers), lists (as they
don't exist, but are modeled by structs containing pointers).
Back to your example: your solution is perfectly fine, although a bit
costly and more error-prone if you happen to forget to create a copy.
A safer alternative for these cases is using tuples, because they are
More information about the Python-list