оператор return не выходит из рекурсивной функции

Question

Я заранее извиняюсь, если уже есть вопрос, отвечающий на эту проблему, но я не нашел ни одного, который бы помог. По сути, у меня есть вложенный словарь с n-уровнями, то есть

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,
            ...,
          }
      }
  }

и ключом, который я хочу удалить, скажем, "lvl_3a_3". Это то, что у меня есть

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

с помощью другого вопроса StackOverflow . Но как только он находит key для удаления и ожидается return d, он продолжает до else состояния вместо полного выхода из функции. Фактически, он запускает else -статист дважды, прежде чем полностью завершиться. Я не уверен, что происходит, за исключением того, что я как-то ссылаюсь на функцию, и поэтому она не возвращается должным образом.

Answer 1

Ваш код работает неправильно, потому что вы return получаете результаты каждого рекурсивного вызова, даже если он не нашел искомый ключ и не внес изменений. Когда ваша функция достигает недопустимого объекта в первый раз (например, внутренний вызов выполняется с недиктивным значением), она возвращает None (по умолчанию), и это распространяется по стеку вызовов, чтобы стать окончательным результатом top- вызов уровня тоже.

Поскольку вы изменяете словарь на месте, вам действительно не следует использовать return для значения словаря. У вызывающей стороны уже есть ссылка на диктовку, над которой вы работаете, поэтому вы можете вместо этого использовать возвращаемое значение, чтобы сообщить, когда вместо этого мы нашли нужный ключ:

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

Примечание. Я переместил немного кода, который удалил пустые словари, чтобы быть в рекурсивном регистре. Это предполагает, что у вас нет пустых словарей, которые вы ожидаете очистить в начале, вы просто не хотите, чтобы удаление последней листовой записи в дикте оставляло кучу потерянных родительских словарей вокруг.

Назовите код следующим образом:

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}}

Последнее замечание: этот код удаляет не более одного ключа. Если вы хотите, чтобы он удалял все вхождения ключа, которые могут появляться несколько раз, вам нужно избавиться от return в рекурсивном случае. На самом деле, вам даже не нужно будет возиться с возвращаемыми значениями вообще в этой ситуации, вы просто будете всегда проверять весь текст безоговорочно.

Answer 2

Вот решение, которое я нашел

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