UnboundLocalError when using recursion in Python?

Question

A simple recursive search is shown below. There seems to be conflicting opinions on whether or not nesting a function is good practice. One MOOC is teaching recursion using the template below but many in the community balk at this approach.

Anyway, if the recursion snippet below is changed from this working version,

# subgroups exist, recurse into each one
for group in groups:
    get_all_users(group)

to this version where the return parameter is captured,

# subgroups exist, recurse into each one
for group in groups:
    users = get_all_users(group)

then the following error occurs:

Traceback (most recent call last):
  File "problem_4.py", line 84, in <module>
    print(is_user_in_group("sub_child_1_user", sub_child_1_group))
  File "problem_4.py", line 53, in is_user_in_group
    users = get_all_users(group)
  File "problem_4.py", line 37, in get_all_users
    users.extend(group.get_users())
UnboundLocalError: local variable 'users' referenced before assignment

This is particularly confusing because that is not the line where the change was made, meaning if the logic fails here it should have failed in the working version. Also the list named "users" is clearly defined before the recursive function is called. My understanding of the variable scope is that the users list is now fully accessible to the nested recursive function, so why is an error thrown about it "being referenced before assignment" in an unexpected place?

class Group:

    # group has a name, users, and children groups
    def __init__(self, name):
        self.name = name
        self.groups = []
        self.users = []

    # simple getters and setters
    def get_name(self):
        return self.name
    def get_groups(self):
        return self.groups
    def get_users(self):
        return self.users
    def add_group(self, group):
        self.groups.append(group)
    def add_user(self, user):
        self.users.append(user)

def is_user_in_group(user, group):
    """
    Return True if user is in the group, False otherwise.

    Args:
      user(str): user name/id
      group(class:Group): group to check user membership against
    """

    # initialize a blank list for output
    users = []

    # recursive function to collect all users in passed group
    def get_all_users(group):

        # add the users on this group level
        users.extend(group.get_users())

        # get the subgroup children of this group
        groups = group.get_groups()

        # base case, there are no subgroups and we are at the lowest level
        if len(groups) == 0:
            return users

        # subgroups exist, recurse into each one
        for group in groups:
            get_all_users(group)

        return users

    # start recursion
    users = get_all_users(group)

    # search through the all collected users
    for _user in users:

        # current user matches passed user
        if user == _user:
            return True

    return False

########## TESTING ##########

# create a few groups
parent_group = Group("parent_group")
child_1_group = Group("child_1_group")
child_2_group = Group("child_2_group")
sub_child_1_group = Group("sub_child_1_group")

# define the group heirarchy
parent_group.add_group(child_1_group)
parent_group.add_group(child_2_group)
child_1_group.add_group(sub_child_1_group)

# add a user to each group level
parent_group.add_user("parent_user")
child_1_group.add_user("child_1_user")
child_2_group.add_user("child_2_user")
sub_child_1_group.add_user("sub_child_1_user")

# check for the presence of the sub_child_1_user in its native sub_child_1_group
print(is_user_in_group("sub_child_1_user", sub_child_1_group))
# True

# the sub_child_1_user is also a member of the parent group
print(is_user_in_group("sub_child_1_user", parent_group))
# True

# check for the presence of a nonexistant user
print(is_user_in_group("sub_child_not_added", child_1_group))
# False

# verify the presence of the parent_user in the top level parent_group
print(is_user_in_group("parent_user", parent_group))
# True

Because now that you have an assignment statement, `users` will be local by default, and as the error states, there is no local `users` — juanpa.arrivillaga, Sep 08 '19 at 22:29
Also, if this Python course is teaching you to write getters take it with a grain of salt — juanpa.arrivillaga, Sep 08 '19 at 22:30
@juanpa.arrivillaga The assignment statement was the key concept, thank you. — apsommer, Sep 10 '19 at 04:44

score 0 · Answer 1 · answered Sep 08 '19 at 23:29

Anytime recursion becomes a problem, my advice is to keep it simple and trust the recursive process. Here's how I might approach your is_user_in_group() function:

def is_user_in_group(user, group):
    """
    Return True if user is in the group, False otherwise.

    Args:
        user(str): user name/id
        group(class:Group): group to check user membership against
    """

    # recursive function to collect all users in passed group
    def get_all_users(group):
        # initialize a blank list for output
        users = []

        # add the users on this group level
        users.extend(group.get_users())

        # get the subgroup children of this group
        groups = group.get_groups()

        # if subgroups exist, recurse into each one
        for group in groups:
            users.extend(get_all_users(group))

        return users

    # start recursion
    users = get_all_users(group)

    # search through the all collected users
    return user in users

A better way to approach this would be to check for user as you recurse so you can halt the recursion if/when you get a positive result and only expand the tree fully in the case of a negative result.

Thank you for this alternate approach. Would you please explain why the original code failed in this unexpected location? — apsommer, Sep 09 '19 at 20:26

UnboundLocalError when using recursion in Python?

1 Answers1