Part of an algorithm course I am taking is to use look through a dictionary of keys and values and continue to look for matching keys & values. For example if there is a matching key, use the value to look up the next key and continue down the rabbit hole. If a match if found more than once to prevent an infinite loop return False else it should return the last key found.

1. Look up a key called "bat", and find a value "pig" then continue
2. Look up a key called "pig", and find "cat" then continue
3. Look up a key called "cat", and find "dog" then continue
4. Look up a key called "dog", and find "ant" then continue
5. Look up a key called "ant", and find no associated value, and so it would return "ant"

This is the data:

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

This is my function below where I am trying learn recursion...and understand why my function doesn't return False when a key saved to MEMORY has a value greater than 2.

def rabbit_hole(dictionry,key,MEMORY={}):
    
    #print(MEMORY)
    
    if key in MEMORY:
        MEMORY[key]  = 1
        
    else:
        MEMORY[key] = 1
        

    for val in MEMORY.values():
        #print(val)

        if val == 2:
            return False # <--- why not working?

    for k,v in dictionry.items():
        if k == key:
            
            # recursive call
            rabbit_hole(dictionry,v,MEMORY)

    #print("return last added dict key")
    return list(MEMORY)[-1]

Any tips appreciated not a lot of wisdom here...if I run:

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

The code above returns:

ant
hen
doe
yak
ram

But its supposed to return a False on rat like this:

ant
hen
doe
yak
False

CodePudding user response：

You are close, this point can help you:

• Your condition to break out of the recursive loop should normally come first, which is if the key is in MEMORY

• You need to return the value of the recursive call thanks Abhinav

In addition, some style/optimisation suggestions:

• If you want to keep track of what you have seen so far, you can use a set over a dict

• Then with a dictionary, you dont need to loop over the keys (that defeats the point of a dictionary). You can just see if a key is in the dictionary, and if it is, get the value.

• Replace the default mutable argument dict with None, and then set it as a dictionary (or set) if it is passed in as None. This is because if you re-run the function:

print(rabbit_hole(d, "bat"))
print(rabbit_hole(d, "bat"))

It will reuse the same dictionary/set which will then have preexisting keys, rather than creating a new dictionary

ant
False

I would suggest you try again with these points, but if not here is a solution:

 def rabbit_hole(dictionary, key, seen=None):
    if seen is None:
        seen = set()

    if key in seen:
        return False

    seen.add(key)

    if key in dictionary:
        return rabbit_hole(dictionary, dictionary[key], seen)
    return key
  

CodePudding user response：

The main issue is, you're not returning the value from the recursive call. As a result, the function returns the last value from the memory list. This simple fix should return the correct value:

    for k,v in dictionry.items():
        if k == key:
            # recursive call
            return rabbit_hole(dictionry,v,MEMORY)