list parameter of a recursive function

Terry Reedy tjreedy at udel.edu
Wed Oct 6 18:12:32 EDT 2010


On 10/6/2010 3:22 PM, TP wrote:
> Hi,
>
> 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 sort of function is an exception. If you add the line below, so 
that you can use just one list, you should just say 'some_list = []' in 
the header.

>
> 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 )
          some_list.pop()
>     # 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!

Uhless you pop items off the stack as you back up!

This is assuming that you do not need to keep the leaf value of the list 
as the funcions works up and back down to the next leaf, and so on. Even 
if you do, it might still be better to copy the working buffer just once 
when you hit the leaf.

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

C sometimes copies values and sometimes passes addresses (pointers, 
references). It does the latter for arrays and functions. I think the 
rule has varied for structs. C and Python have quite different 
name-object-value models.

Python calls functions by binding argument objects to parameter names.
Unlike C assignment, Python name binding never copies objects.

CPython implements binding by directly associating name and object 
address. It also does not use a garbage collector that move objects 
around in memory. Other implementation do differently.

-- 
Terry Jan Reedy




More information about the Python-list mailing list