"return" statement not exiting recursive function

Question

I apologize in advance if there's already a question answering this problem but I didn't find any that helped. Essentially, I have a nested dictionary with n-levels, i.e.,

nested_dict = {
    "lvl_1a": {
        "lvl_2a_1": {
            "lvl_3a_1": 1,
            "lvl_3b_1": 2,
            ...,
         },
        "lvl_2b_1": {
            "lvl_3a_2": 5,
            "lvl_3b_2": 6,
             ...,
        },
     "lvl_1b": {
         "lvl_2a_2": {
            "lvl_3a_3": 1,
            "lvl_3b_3": 2,
            ...,
          }
      }
  }

and a key I want to remove, say that is, "lvl_3a_3". This is what I have so far

def remove_a_key(d, remove_key):
    if isinstance(d, dict) and d:
        for key in list(d.keys()):
            if key == remove_key:
                del d[key]
                return d

            elif not d[key]:
                del d[key]
                return remove_a_key(d, remove_key)

            else:
                return remove_a_key(d[key], remove_key)

modified_dictionary = remove_a_key(nested_dictionary, "lvl_3a_3")

with the help of another StackOverflow question. But once it finds the key to remove, and return d is expected, it continues to the else-statement instead of completely exiting out of the function. In fact, it runs the else-statement twice before completely exiting out. I'm not sure what's going on except that somehow I'm referencing the function and thus it's not returning properly.

Please repeat the intro tour, especially [MRE](https://stackoverflow.com/help/minimal-reproducible-example). Your posted code merely defines a function and quits without executing. — Prune, Apr 01 '20 at 20:42
Keep in mind that `return` returns *one* level. The outer stack frame picks up execution; if that layer doesn't choose to do a return, then other code executing is expected. Though since in the given code every instance of `remove_a_key` *does* immediately return, I'd really want to see a real reproducer in order to believe that the description of the problem given in the question is in accurate one rather than a misreading of the symptoms presented. — Charles Duffy, Apr 01 '20 at 21:03
That said, I don't know how you expect this function to do anything useful. If you always `return` during the first iteration over a list (thus, when `key` refers only to the *very first* key), how do you expect other members of that list (or, in this context, other keys in that dict) to be processed? — Charles Duffy, Apr 01 '20 at 21:05
I also don't know why you'd want to recurse after you *do* do a successful removal, *in the same case that recursing after a removal will always recreate*. That seems like a fast route to an endless loop. — Charles Duffy, Apr 01 '20 at 21:07

score 2 · Accepted Answer · answered Apr 01 '20 at 21:24

Your code is not working correctly because you return the results of every recursive call, even if it didn't find the sought-after key and made no changes. The first time your function reaches an invalid object (e.g. an inner call gets made on a non-dict value), it returns None (by default), and that propagates up the call stack to be the final result of the top-level call too.

Since you're modifying the dictionary in place, you really shouldn't be using return for the dictionary value. The caller already has a reference to the dict you're working on, so you can instead use the return value to signal when we've found the key we want instead:

def remove_a_key(d, remove_key):
    if isinstance(d, dict) and d:
        for key in list(d.keys()):
            if key == remove_key:
                del d[key]
                return True                          # first base case, we found the key

            else:                                    # recursive case
                if remove_a_key(d[key], remove_key): # only return if we were successfull 
                    if not d[key]:   # empty dict cleanup code
                        del d[key]
                    return True      
    return False                                     # third base case, failure

Note, I moved the bit of code that removed empty dictionaries to be inside the recursive case. This assumes you don't have any empty dictionaries that you expect to be cleaned up at the start, you just don't want the removal of the last leaf entry in a dict to leave a bunch of orphaned parent dictionaries around.

Call the code like this:

nested = {
          "a": {"aa": 1, "ab": 2},
          "b": {"ba": 3, "bb": 4},
         }
print(nested) # prints {'a': {'aa': 1, 'ab': 2}, 'b': {'ba': 3, 'bb': 4}}
remove_a_key(nested, "bb")
print(nested) # prints {'a': {'aa': 1, 'ab': 2}, 'b': {'ba': 3}}
remove_a_key(nested, "ba")
print(nested) # prints {'a': {'aa': 1, 'ab': 2}}

A final note: This code only ever removes at most one key. If you want it to remove all occurrences of a key that might appear multiple times, you'll need to get rid of the return in the recursive case. In fact, you won't even need to mess with return values at all in that situation, you'd just always scan the whole dict, unconditionally.

score 1 · Answer 2 · answered Apr 01 '20 at 21:27

Here's a solution I found

def remove_key(d = {}, q = ""):
  if isinstance(d, dict):            # <-- only attempt prune on dict
    if q in d:
      del d[q]                       # <-- remove key if it exists
    for (key, value) in d.items():
      d[key] = remove_key(value, q)  # <-- recur
  return d                           # <-- always return d

"return" statement not exiting recursive function

2 Answers2