Recursive function on mutable object

Question

I am trying to build all paths recursively in a class. Here is what I have so far:

def get_paths(self, component=None, current_path=None, all_paths=None):

    # set defaults
    if component is None: 
        component = self._ground; 
        current_path = [component,]

    ##### [START] RECURSIVE PART #####

    # get parents of component
    parents = component.parents()

    # if no parents (an endpoint/leaf), add the current_path
    if not parents:
        all_paths.append(current_path)

    # if parents ==> recurse
    # note: because we're starting from the ground and getting all parents
    # we insert the parent before the current path (not after, like if we
    # were recursively getting files in a directory)
    else:
        for parent in parents:
            self.get_paths(parent, [parent,] + current_path), all_paths)

    ##### [END] RECURSIVE PART #####

    # Note that the recursion doesn't 'return' anything, it only modifies
    # the list. We still have to return the list by the method at the end.      
    return all_paths

What this does is it starts at the 'ground' and then recurses up until the element does not have any parents. My question is whether this is a common way to do recursion -- to not actually return anything in the 'recursive part' but just to modify the mutable element (the list here) and then return the result later.

If the above isn't ideal, what would be an example of how it can be improved? Or, what are other ways in which to return a list of paths (the above is very similar to what the $ find ./ would do getting a list of paths).

Never use a list (or other mutable value) as a default argument. all_paths will be defined once when you define the function and then subsequent calls to the function will modify that list. Effectively you can only call the function once. You need to set it to None and then check for it and set the result to [] in the function body. — user3064538
– user3064538, Commented Feb 18, 2020 at 1:20
@Boris thanks for pointing that out. I learned that the hard way with trying to debug this when it was passing [] instead of None. Thank you. Also, I updated the question with that change, as I'm looking more for an answer to the general structure/function of modifying the elements — David542
– David542, Commented Feb 18, 2020 at 1:27

martineau · Accepted Answer · 2020-02-19 08:42:37Z

1

A simple way to do it would be to have a public "interface" method that calls a private recursive method.

Something along these lines:

class Klass:

    _ground = 'ground'

    # Public method.
    def get_paths(self, component=None, current_path=None):
        all_paths = []
        self._get_paths(all_paths, component, current_path)  # Call private method.
        return all_paths

    # Private method.
    def _get_paths(self, all_paths, component=None, current_path=None):
        # Modifies all_paths - executed for that side-effect.    

        # set defaults
        if component is None:
            component = self._ground;
            current_path = [component,]

        # get parents of component
        parents = component.parents()

        # if no parents (an endpoint/leaf), add the current_path
        if not parents:
            all_paths.append(current_path)
        else:
            for parent in parents:
                self._get_paths(parent, [parent,] + current_path), all_paths)

edited Feb 19, 2020 at 8:42

answered Feb 18, 2020 at 1:47

martineau

124k29 gold badges181 silver badges319 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

David542 Over a year ago

why not remove the default args in the method if we know what we're going to pass to it?

martineau Over a year ago

@David542: Would probably be OK to do for the private method.

Collectives™ on Stack Overflow

Recursive function on mutable object

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related