Рекурсия в Python
Имеется многоуровневый словарь.
Вводные данные, искомый ключ.
Цель, найти ключ путем рекурсии.
В общем и целом, что такое рекурсия я понимаю, но я не понимаю почему то что я пишу, не работает так как задумано мною.
Имеется код:
def search(site, search_key, deep=0):
if deep != -1:
print('ГЛУБИНА РЕКУРСИИ', deep)
for i_key, i_value in site.items():
print('\t\t\t\t', i_key)
print('\t\t\t\t', i_value)
if search_key == i_key:
return 'Искомый ключ', i_key
elif isinstance(i_value, dict):
print(isinstance(i_value, dict), i_key, 'is dict')
search(site[i_key], search_key, deep + 1)
else:
print(isinstance(i_value, dict), i_key, 'is not dict')
deep в данном случае по назначению не используется*
Иду циклом по объектам словаря.
Если значение ключа это словарь(isinstance(i_value, dict), то он его проверяет, это сделано чтобы он не проверял побуквенно значения ключей которые являются просто строкой.
Если он циклом не нашел искомый ключ он идет соответственно в блок elif: где вызывает рекурсию словаря от ключа. По факту цикл не закончился, а прервался(заморозился) из-за рекурсии на первом же ключе(т.е. при возврате он должен продолжить его).
И вот тут меня вынесло на 2 дня. Если я вызываю рекурсию с return как положено, то он стопарится в первом же блоке ключа. Т.е у меня словарь состоит из 2 ключей на 1-м уровне, он проверяет первый, а на второй забивает даже на обратном пути. И выдает None, ибо то что на тот момент я ищу, находится во втором ключе.
ГЛУБИНА РЕКУРСИИ 0
html
{'head': {'title': 'Мой сайт'}, 'body': {'h2': 'Здесь будет мой заголовок', 'div': 'Тут, наверное, какой-то блок', 'p': 'А вот здесь новый абзац'}}
True html is dict
ГЛУБИНА РЕКУРСИИ 1
head
{'title': 'Мой сайт'}
True head is dict
ГЛУБИНА РЕКУРСИИ 2
title
Мой сайт
False title is not dict
None
Если же, в рамках эксперимента, убрать return, то как мною и задумано, после окончания рекурсии для первого ключа, он идет во второй ключ, ииии?) Он находит искомое мною значение, но выдает None, потому что что? А потому что функция на тот момент ничего не возвращает, ибо return нету.
ГЛУБИНА РЕКУРСИИ 0
html
{'head': {'title': 'Мой сайт'}, 'body': {'h2': 'Здесь будет мой заголовок', 'div': 'Тут, наверное, какой-то блок', 'p': 'А вот здесь новый абзац'}}
True html is dict
ГЛУБИНА РЕКУРСИИ 1
head
{'title': 'Мой сайт'}
True head is dict
ГЛУБИНА РЕКУРСИИ 2
title
Мой сайт
False title is not dict
body
{'h2': 'Здесь будет мой заголовок', 'div': 'Тут, наверное, какой-то блок', 'p': 'А вот здесь новый абзац'}
True body is dict
ГЛУБИНА РЕКУРСИИ 2
h2
Здесь будет мой заголовок
False h2 is not dict
div
Тут, наверное, какой-то блок
None
Я целиком и полностью, просто не могу понять что тут не так.
Почему при вызове рекурсии с return он зависает на первом ключе и не идет во второй?
*на этот момент искомым ключом был div, и в варианте без return последним блоком выходит он в паре с None
Имеющийся словарь пришлось добавить в качестве дополнения.
Проблема с вашим кодом
Возврат из рекурсии: Когда вы вызываете рекурсию, вам нужно обрабатывать результат рекурсивного вызова. Если рекурсивный вызов нашел ключ, вам нужно прекратить дальнейшее выполнение и вернуть результат.
Отсутствие возврата в цикле: Если рекурсивный вызов ничего не возвращает, текущий вызов функции тоже должен ничего не возвращать. Нужно корректно обрабатывать результат внутри цикла.
def search(site, search_key, deep=0):
if deep != -1:
print('ГЛУБИНА РЕКУРСИИ', deep)
for i_key, i_value in site.items():
print('\t\t\t\t', i_key)
print('\t\t\t\t', i_value)
if search_key == i_key:
return 'Искомый ключ', i_key, i_value
elif isinstance(i_value, dict):
print(isinstance(i_value, dict), i_key, 'is dict')
result = search(i_value, search_key, deep + 1)
if result:
return result
else:
print(isinstance(i_value, dict), i_key, 'is not dict')
return None
site = {
'html': {
'head': {
'title': 'Мой сайт'
},
'body': {
'h2': 'Здесь будет мой заголовок',
'div': 'Тут, наверное, какой-то блок',
'p': 'А вот здесь новый абзац'
}
}
}
result = search(site, 'div')
print(result) Объяснение исправлений
Рекурсивный вызов с обработкой результата:
result = search(i_value, search_key, deep + 1) — сохраняем результат рекурсивного вызова.
if result: — если результат не None, возвращаем его.
Возврат результата в случае нахождения ключа:
return 'Искомый ключ', i_key, i_value — возвращаем ключ и значение при нахождении.
Возврат None, если ключ не найден:
Добавлен возврат None в конце функции, если ключ не найден на всех уровнях.