-1

TL;DR at the end!

Hi, I'm having a problem with a recursive function and a dictionary that is supposed to return a value when a specific key is found, but all I'm getting is None.

Let's suppose that I'm building a game that runs on localhost:8080/MyGame/ and I have HTML files that can go at the end of that address, like localhost:8080/MyGame/Archer.html.

I'm going to build my HTML link with localhost:8080/MyGame/ + Archer.html, and I have a dictionary that contains the base for it and the values for each page, like Archer.html or Knight/Main_Castle.html with archer_sc and knight_sc as the keys for it, respectively ("sc" stands for Secondary Castle, and "mc" for Main Castle)

I've made a python file to further express the problem that I'm having, and it contains the dictionary that I'm trying to iterate over, the recursive function and the main method

So, my dictionary looks like this:

URLS = {
    'base': 'localhost:8080/MyGame/',
    'main_castle': {
        'defenses_mc': {
            'bombard_tower_mc': 'Bombard_Tower.html',
            'fire_roaster_mc': 'Fire_Roaster.html',
            'freeze_tower_mc': 'Freeze_Tower.html'
        },
        'army_mc': {
            'troops_mc': {
                'mage_mc': 'Mage.html',
                'witch_mc': 'Witch.html',
                'knight_mc': 'Knight/Main_Castle.html',
                'berserker_mc': 'Berserker/Main_Castle.html',
            },
            'commandants': {
                'wizard_mc': 'Wizard.html',
                'warlock_mc': 'Warlock.html',
                'dragon_mc': 'Dragon.html'
            },
            'spells': {
                'upgrade_spell': 'Upgrade_Spell.html',
                'damage_spell': 'Damage_Spell.html'
            }
        },
    },
    'secondary_castle': {
        'defenses_sc': {
            'archer_tower_sc': 'Archer_Tower.html',
            'barracks': 'Barracks.html'
        },
        'army_sc': {
            'troops_sc': {
                'archer_sc': 'Archer.html',
                'knight_sc': 'Knight/Secondary_Castle.html',
                'berserker_sc': 'Berserker/Secondary_Castle.html'
            }
        }
    }
}

and my recursion function looks like this:

def recursion(dictionary, key_to_find):
    for key, value in dictionary.items():
        if key_to_find == key:
            print("Found! '" + key_to_find + "' value is '" + value + "'")
            return value
        elif isinstance(value, dict):
            recursion(value, key_to_find)
    return "Sorry, couldn't find anything :("

One thing to note that I'm going to mention later: The code above iterates through the ENTIRE dictionary.

The recursive funcion takes two arguments: A dictionary that I want to iterate through, and a specific key that I want to find it's value.

The main function looks like this:

def main():
    knight_sc = str(recursion(URLS, 'knight_sc'))
    knight_sc_url = URLS['base'] + knight_sc
    print(knight_sc_url)

It is expected that knight_sc would be equal to 'Knight/Second_Castle.html', since when I run the recursive function it actually FINDS and prints the actual value of the key knight_sc which is 'Knight/Second_Castle.html', but it only returns None

Here's the thing, I've searched about it and everywhere it says that you can't simply call a function inside another function and call it recursive, since that would likely just be functionA calling functionB and so on…

However when I put the return before calling the function on

elif isinstance(value, dict):
    recursion(value, key_to_find) # <- return should go at the start of this line

it only iterates to freeze_tower_mc and it stops iterating there. At least the version WITHOUT the return in the function call would iterate throught the entire dictionary, find that the key is equal to key_to_find and print it's value, but not return the value.

If I, for example, call recursion() WITH the return tag before calling recursion(), but now passing 'fire_roaster_mc' in my main method as a argument, it actually returns 'Fire_Roaster.html' and I can build the HTML link utilizing URLS['base'] + str(recursion(URLS, 'fire_roaster_mc'))

Am I really missing something stupid that I can't see because my mind went numb after so many tries and nothing working or is this a common issue? Is there a fix for this?

Also I should say that I'm very new to Python, coming from Java, and I just like to code for fun(never done something serious like for a job, project or college) and so far I've really liked Python for it's simpleness and easiness :D

TL;DR: My recursive function that's supposed to return a value if a specific key is found is returning None, but it's finding the actual key and I can print it's value

Sorry for any grammatical errors, for english isn't my mother tongue.

Thanks in advance!

Henrique Siqueira
  • 1
  • 1
  • 1
    OT: It's good practice to put **tl;dr:** on top of a question as well an answer, followed by details :) – wiesion Jun 23 '18 at 20:45
  • 2
    You're ignoring the recursion result. Needs to be `return recursion(value, key_to_find)`... If that's not working, the error is elsewhere, but that is needed – OneCricketeer Jun 23 '18 at 20:45
  • @cricket_007 when I put `return` before it, it only iterates to a specific key, which is the 'freeze_tower_mc' key, and after that, instead of going to the next dictionary which is 'army_mc', it just stops iterating. Maybe a logic error? – Henrique Siqueira Jun 23 '18 at 20:51
  • in the second call of `recursion()` you are ignoring the return value , and you function continue executing the loop. you should add an if statement after the second `recursion()` to check if the value found or not . – Ali Aqrabawi Jun 23 '18 at 20:57
  • You need to `return` your recursive call to `recursion`. You also need to continue to iterate if the key is not found in the recursive call. And better raise an exception when the key is not found. def recursion(dictionary, key_to_find): for key, value in dictionary.items(): if key_to_find == key: return value if isinstance(value, dict): try: return recursion(value, key_to_find) except RuntimeError: pass raise RuntimeError('Key not found') – blhsing Jun 23 '18 at 20:57
  • First, it is inefficient that you are iterating through the whole dictionary. You could flatten it out with a preparation step, and use that dictionary to perform lookups. Second, try thinking through what you want in plain English (or whatever, the point is NOT in code), then do that in code. You want to return right away if you found a result, but keep iterating if you didn't ... so do that. (And return None if there is no answer. Let the caller write the detailed apology.) – Kenny Ostrom Jun 23 '18 at 21:00
  • https://stackoverflow.com/questions/14962485/finding-a-key-recursively-in-a-dictionary – NobbyNobbs Jun 23 '18 at 21:02
  • Yeah, the question linked by @NobbyNobbs has a answer by Becca Petrin with the method `get_recursively()` that returns a list which you can access, if something was found, with the index 0. Boy oh boy it's going to take a while for me to grasp how it works :( My issue has been resolved, do I mark it as solved then? – Henrique Siqueira Jun 23 '18 at 21:28

1 Answers1

0

It stops at freeze_tower_mc because that's the inner most dictionary, and you've returned Sorry, couldn't find anything because you've looped over all elements of that dictionary. The return result is then passed back up the call stack, which ends the loop.

I think instead, if you want to track that you've not found anything within the entire dictionary, pass in a depth parameter, and only return you didn't find anything when that loop is over and you're back at the top of the dictionary 

def recursion(dictionary, key_to_find, depth=0):
    for key, value in dictionary.items():
        if key_to_find == key:
            print("Found! '{}' value is '{}'".format(key_to_find, value)) 
            return value
        elif isinstance(value, dict):
            print("Searching " + str(value) + " at depth " + str(depth+1)) 
            found = recursion(value, key_to_find, depth=depth+1)
            if found is not None:
                # if it is found, you'd see this line printed twice, once in the recursion, then once here 
                print("Found! '{}' value is '{}'".format(key_to_find, found)) 
                return found
    if depth == 0:
        return "Sorry, couldn't find anything"
OneCricketeer
  • 179,855
  • 19
  • 132
  • 245