Блог

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

Я протестировал следующий код, но он не возвращается должным образом ни для каких рекурсивных примеров. Я добавил два оператора печати для тестирования, и, похоже, он работает правильно, но return не передает правильный результат, например, 1 и 2 (возвращает «None»). Я попытался переместить 2-й оператор возврата на один блок, но затем он вернул первый цикл функции. Я полагаю, что могу переписать, чтобы использовать print, а не return, но проблема требует использовать return.

Буду признателен за любую помощь и объяснения.

 def rabbit_hole(D, Key):
    if Key in D: 
        if D[Key] in D:
            if D[D[Key]] == Key:
                return False
            else:
                print("F1 /", D[Key])
                rabbit_hole(D, D[Key])
        else:
            print("F2 /", D[Key])
            return D[Key]
    else: return Key

d = {"bat": "pig", "pig": "cat", "cat": "dog", "dog": "ant", "cow": "bee", "bee": "elk", "elk": "fly", "ewe": "cod", "cod": "hen", "hog": "fox", "fox": "jay", "jay": "doe", "rat": "ram", "ram": "rat"}

print(rabbit_hole(d, "bat"))
print(rabbit_hole(d, "ewe"))
print(rabbit_hole(d, "jay"))
print(rabbit_hole(d, "yak"))
print(rabbit_hole(d, "rat"))
  

Спасибо всем, кто прокомментировал. Я отредактировал код следующим образом, что решило проблему и кажется более упорядоченным. Обратите внимание, что первый оператор if предназначен специально для решения возможного цикла, который специально включен в пример и где проблема запрашивает возврат False, если встречается.

     def rabbit_hole(D, Key):
        if Key in D and D[Key] in D:
            if D[D[Key]] == Key:  return False
            return rabbit_hole(D, D[Key])
        elif Key in D: return rabbit_hole(D, D[Key])
        return Key
  

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

Вы также усложнили проблему, чем кажется. Рассмотрим:

 def rabbit_hole(dictionary, string):
    if string in dictionary:
        return rabbit_hole(dictionary, dictionary[string])

    return string

dictionary = {
    'bat': 'pig', 'pig': 'cat', 'cat': 'dog', 'dog': 'ant',
    'cow': 'bee', 'bee': 'elk', 'elk': 'fly', 'ewe': 'cod',
    'cod': 'hen', 'hog': 'fox', 'fox': 'jay', 'jay': 'doe',
    'rat': 'ram', 'ram': 'rat'
}

print(rabbit_hole(dictionary, 'bat'))
print(rabbit_hole(dictionary, 'ewe'))
print(rabbit_hole(dictionary, 'jay'))
print(rabbit_hole(dictionary, 'yak'))
print(rabbit_hole(dictionary, 'rat'))
  

Обратите внимание, что предоставленная вами последняя тестовая строка 'rat' вызовет бесконечную рекурсию цикла из-за словарных записей:

 'rat': 'ram', 'ram': 'rat'
  

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

Обратите внимание, проблема с циклом существует по замыслу в проблеме — моим решением был первый блок кода, который проверяет, что 2-е значение равно первому ключу (который, как я полагаю, не элегантен и может быть сжат, но, похоже, работает)

Рассмотрим {«rat»: «ram», «ram»: «ошибка», «bug»: «rat»} — вы не можете предсказать, как далеко заглядывать вперед. Пара выходов: используйте try ... except RecursionError: блок:

 def rabbit_hole(dictionary, string):
    try:
        if string in dictionary:
            return rabbit_hole(dictionary, dictionary[string])

        return string
    except RecursionError:
        return False
  

Или используйте свой собственный счетчик глубины вызова и сравните его с длиной словаря, чтобы определить, что вы исчерпали все возможности и должны выполнять рекурсию:

 def rabbit_hole(dictionary, string, depth=0):
    if depth > len(dictionary):
        return False

    if string in dictionary:
        return rabbit_hole(dictionary, dictionary[string], depth   1)

    return string
  

Вот простой способ сделать это. Используйте блоки try и except . Используйте try , чтобы попытаться найти значение, связанное с ключом. Если значение найдено, повторите процесс рекурсивно, снова вызвав rabbit_hole функцию. Если значение не найдено, возникает KeyError значение, которое перехватывается except блоком и возвращает самый последний ключ.

 def rabbit_hole(D, Key):
    try:
        new_key = D[Key]
        return rabbit_hole(D, new_key)
    except:
        return Key

d = {"bat": "pig", "pig": "cat", "cat": "dog", "dog": "ant", 
     "cow": "bee", "bee": "elk", "elk": "fly", "ewe": "cod",
     "cod": "hen", "hog": "fox", "fox": "jay", "jay": "doe",
     "rat": "ram", "ram": "rat"}

print(rabbit_hole(d, "bat"))
print(rabbit_hole(d, "ewe"))
print(rabbit_hole(d, "jay"))
print(rabbit_hole(d, "yak"))
print(rabbit_hole(d, "rat"))
  

 ant
hen
doe
yak
ram