CODEWITHSUNDEEP
pythonrecursionreturn
PY78
PY78

Reputation: 41

Trouble with return function - not working with recursive code

I am trying to complete the following problem: Write a function called rabbit_hole. rabbit_hole should have two parameters: a dictionary and a string. The string may be a key to the dictionary. The value associated with that key, in turn, may be another key to the dictionary. Keep looking up the keys until you reach a key that has no associated value. Then, return that key.

I tested the following code, but it does not return properly for any recursive examples. I added two print statements for testing and it seems to flow correctly, but return is not propagating the correct result for example 1 and 2 (returning "None"). I tried moving the 2nd return statement over one block but it then returned the first cycle of the function. I believe can rewrite to use print rather than return, but the problem asks to use return.

Appreciate any help and explanation.

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

Upvotes: 3

Views: 278

Answers (3)

cdlane
cdlane

Reputation: 41872

You've made a common recursion beginner's error. If your recursive function returns a value, and you call it recursively, you need to deal with its return value, even if it's just to pass it on via another return. You can't simply ignore it.

You've also made the problem more difficult than it seems. Consider:

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

Note that the final test string you've provided, 'rat', will cause an infinite loop recursion-wise due to the dictionary entries:

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

and generate a Python error. By design, it should fail this way.

Note, the loop issue is there by design in the problem - my solution was the first block of code which tests for the 2nd value being equal to the first key (which I imagine is not elegant and can be condensed, but seemed to work)

Consider {"rat": "ram", "ram": "bug", "bug": "rat"} -- you can't predict how far to look ahead. A couple of ways out: use a try ... except RecursionError: block:

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

        return string
    except RecursionError:
        return False

Or, use your own calling depth counter and compare it to the length of the dictionary to determine that you've exhausted all possibilities and must be recursing:

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

Upvotes: 1

PY78
PY78

Reputation: 41

Thanks for all who have commented. I have edited the code as follows, which has solved the issue and seems more streamlined. Note, the first if statement is specifically to solve for the possible loop, which is included purposefully in the example and where the problem asks for a return of False if encountered.

    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

Upvotes: 1

ProteinGuy
ProteinGuy

Reputation: 1942

Here's a simple way to do this. Use try and except blocks. Use try to attempt to find the value associated with a key. If a value is found, repeat the process recursively by calling the rabbit_hole function again. If no value is found, a KeyError is raised which is caught by the except block and returns the most recent Key.

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

Upvotes: 0

Related Questions