How to use properly recursion and side effects in python

Question

In a tree structure, I'm trying to find all leafs of a branch. Here is what I wrote:

def leafs_of_branch(node,heads=[]):
    if len(node.children()) == 0:
        heads.append(str(node))
    else:    
        for des in node.children():
           leafs_of_branch(des)
    return heads


leafs_of_branch(node)

I don't know why but it feels wrong for me. It works but I want to know if there is a better way to use recursion without creating the heads parameter.

Answer 1

I believe this should work:

def leafs_of_branch(node):
    if len(node.children()) == 0:
       return [str(node)]
    else:
       x = []
       for des in node.children():
           x += leafs_of_branch(des)  #x.extend(leafs_of_branch(des)) would work too :-)
       return x

It's not very pretty and could probably be condensed a bit more, but I was trying to keep the form of your original code as much as possible to make it obvious what was going on.

Your original version won't actually work if you call it more than once because as you append to the heads list, that list will actually be saved between calls.

Answer 2

This

def leafs_of_branch(node,heads=[]):

is always a bad idea. Better would be

def leafs_of_branch(node,heads=None):
    heads = heads or []

as otherwise you always use the same list for leafs_of_branch. In your specific case it might be o.k., but sooner or later you will run into problems.

I recommend:

def leafs_of_branch(node):
    leafs = []
    for des in node.children():
        leafs.extend(leafs_of_branch(des))
    if len(leafs)==0:
        leafs.append(str(node))
    return leafs

leafs_of_branch(node)

Instead of doing a if len(node.children()==0, I check for len(leafs) after descending into all (possibly zero) children. Thus I call node.children() only once.

Answer 3

As long as recursion goes, you are doing it right IMO; you are missing the heads paramater on the recursive call tho. The reason it's working anyway is for what other people said, default parameters are global and reused between calls.

If you want to avoid recursion altogheter, in this case you can use either a Queue or a Stack and a loop:

def leafs_of_branch(node):
    traverse = [node]
    leafs = []

    while traverse:
        node = traverse.pop()
        children = node.children()

        if children:
            traverse.extend(children)
        else:
            leafs.append(str(node))

    return leafs

Answer 4

You may also define recursively an iterator this way.

def leafs_of_branch(node):
    if len(node.children()) == 0:
        yield str(node)
    else:    
        for des in node.children():
            for leaf in leafs_of_branch(des):
                yield leaf

leafs = list(leafs_of_branch(node))

Answer 5

First of all, refrain from using mutable objects (lists, dicts etc) as default values, since default values are global and reused between the function calls:

def bad_func(val, dest=[]):
    dest.append(val)
    print dest

>>> bad_func(1)
[1]
>>> bad_func(2)
[1, 2]  # surprise!

So, the consequent calls will make something completely unexpected.

As for the recursion question, I'd re-write it like this:

from itertools import chain

def leafs_of_branch(node):
    children = node.children()
    if not children:  # better than len(children) == 0
        return (node, )

    all_leafs = (leafs_of_branch(child) for child in children)
    return chain(*all_leafs)