Trouble with return function - not working with recursive code

Question

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

return rabbit_hole(D, D[Key])

Klaus D.
– Klaus D.

2020-09-10 04:23:22 +00:00
Commented Sep 10, 2020 at 4:23 — Klaus D.
– Klaus D., Commented Sep 10, 2020 at 4:23

PY78 · Accepted Answer · 2020-09-11 17:36:32Z

1

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

answered Sep 11, 2020 at 17:36

PY78

412 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

cdlane · Accepted Answer · 2020-09-11 20:14:04Z

1

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

edited Sep 11, 2020 at 20:14

answered Sep 10, 2020 at 6:09

cdlane

42.2k5 gold badges37 silver badges87 bronze badges

7 Comments

ProteinGuy Over a year ago

The infinite recursion loop can be avoided by a try/except block.

cdlane Over a year ago

@JafetGado, I don't believe the infinite recursin loop can be avoided by a try/except block, only the error exit at the end of it. The try/except block will catch the RecursionError after 1000 or so loops have occured, and allow you to exit gracefully if desired.

ProteinGuy Over a year ago

I wrote the try/except block to catch the KeyError, but it also catches the RecursionError. Do you have a way to avoid unnecessary recursion in the code?

PY78 Over a year ago

Hello. thank you for the response and clarification. 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)

cdlane Over a year ago

@PY78, 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. Or, use use your own calling depth counter and compare to the length of dictionary to determine that you've exhausted all possibilities and must be recursing.

|

ProteinGuy · Accepted Answer · 2020-09-10 22:05:55Z

0

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

edited Sep 10, 2020 at 22:05

answered Sep 10, 2020 at 6:10

ProteinGuy

1,9622 gold badges22 silver badges39 bronze badges

1 Comment

Stef Over a year ago

The try/except loop looks strongly like it's there solely to catch the KeyError raised by D[key], but it also silently catches the RecursionError in one of the test cases...

Collectives™ on Stack Overflow

Trouble with return function - not working with recursive code

3 Answers 3

Comments

7 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

7 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related