PLEASE HELP! I cannot seem to get to the level of understanding required to answer this question. I have attached book3 as it is the book my function fails to work with.

Must be done with recursion. The technique I'm looking for should only require a definition of 8-12 LINES

Question 4 (9 points): Purpose: To practice recursion on a more interesting problem. Degree of Diculty: Tricky. Pokemon are fantastic creatures that can evolve2 into other, usually stronger, creatures. In their secret laboratory, the evil Team Rocket has been trying to evolve Pokemon in terrifying new ways! Might it now be possible for a meek Magikarp to evolve all the way into the mighty Mewtwo? Your job is to to write a program that uses the power of recursion to nd out. For this problem, you will be given a pokemon evolution book as a dictionary. The keys to this dictionary are pokemon names, and the value for each key is a list of pokemon that can be evolved into. The following is a sample of what this dictionary might look like: book = { " squirtle " : [" wartortle "], " wartortle " : [" blastoise "], " blastoise " : [], " eevee " : [" flareon ", " jolteon ", " vaporeon "] } In the example above, squirtle can (eventually) evolve into a blastoise by rst evolving into a wartortle, but never into an eevee. On the other hand, eevee can evolve into any one of areon, jolteon or vaporeon. Note that a pokemon that can no longer evolve might be in the book and associated with an empty list (like blastoise above) or might not be in the book at all. Either case is ne and your program needs to handle both cases correctly. You are guaranteed, however, that the pokemon book will be structured such that a pokemon cannot "devolve" into itself. Thus, if pokemon A can, either directly or indirectly, evolve into pokemon B, then it will not be possible for B to evolve back into A. Your task is to write a recursive function that will answer the question of whether a source pokemon can eventually evolve into a given target pokemon. Your function should have 3 parameters: the source, the target and the pokemon dictionary to use to check for possible evolutions. Your function should return True if it is possible for source to become the target and False otherwise. This might sound a little dicult, but with the power of recursion, this is not a complicated problem. Your function should be approximately 12 lines of code (not counting comments) and possibly less (ours is 8). If you nd your solution is getting any longer than that, you are overthinking it! Note: For this question, you ARE allowed to use loops as part of your recursive function! You will likely use a loop to iterate over the lists that are in the evolution book. But your program should still use recursion to do the "real work" (in fact, this problem would be MUCH more dicult to solve without using recursion at all!!). 2The Pokemon franchise was in fact extremely scientically irresponsible to use this term. Evolution occurs at the population level, not

book3 = { 'cubone': ['dragonite', 'magmar', 'tangela'], 'krabby': ['vaporeon', 'chansey', 'zapdos', 'electabuzz'], 'spearow': ['mewtwo', 'seadra', 'tentacool'], 'primeape': ['weepinbell', 'hitmonchan', 'mew', 'porygon', 'dewgong'], 'snorlax': ['moltres', 'dragonair', 'dratini', 'mewtwo', 'mew'], 'wartortle': ['rattata', 'weepinbell', 'seaking'], 'flareon': ['porygon', 'dratini', 'articuno'], 'clefairy': ['staryu'], 'rattata': ['bellsprout', 'nidorino'], 'machoke': ['staryu', 'bellsprout'], 'vileplume': ['doduo', 'victreebel', 'machop', 'starmie', 'kabuto'], 'dugtrio': ['golem', 'kadabra', 'rapidash', 'hitmonchan', 'aerodactyl'], 'venusaur': [], 'bulbasaur': [], 'onix': ['horsea'], 'weezing': ['snorlax'], 'beedrill': ['grimer', 'bellsprout', 'clefable', 'arbok'], 'butterfree': ['persian', 'dragonair', 'machop', 'starmie', 'dodrio'], 'charmeleon': ['oddish', 'seel', 'persian', 'seaking', 'poliwrath'], 'paras': ['seadra'], 'raticate': ['raichu', 'voltorb', 'sandshrew'], 'gyarados': ['articuno', 'moltres', 'flareon', 'dratini'], 'mr.mime': [], 'kabutops': ['dragonite', 'aerodactyl', 'mewtwo', 'dragonair'], 'poliwhirl': ['golem', 'graveler', 'magikarp', 'electabuzz', 'mr.mime'], 'muk': ['tauros', 'omanyte', 'mewtwo', 'electrode', 'cubone'], 'rapidash': ['gyarados', 'electrode'], 'golem': [], 'rhydon': ['jynx'], 'zapdos': ['dragonair', 'mewtwo', 'dratini'], 'golduck': ['hypno', 'dewgong', 'jolteon', 'poliwag'], 'gengar': ['jolteon', 'seaking', 'jynx'], 'arcanine': [], 'mew': [], 'gloom': [], 'vulpix': ['wigglytuff'], 'articuno': ['mew', 'zapdos', 'dragonair'], 'ponyta': ['eevee', 'tauros', 'mr.mime', 'horsea'], 'pinsir': ['ditto', 'zapdos'], 'grimer': ['kabutops'], 'nidoqueen': [], 'tangela': ['horsea', 'scyther', 'pinsir', 'kabutops', 'mewtwo'], 'ivysaur': ['marowak', 'krabby', 'growlithe'], 'electabuzz': ['gyarados', 'ditto', 'kabutops', 'porygon'], 'weedle': ['raichu', 'mew', 'snorlax', 'voltorb'], 'omanyte': ['mewtwo', 'zapdos'], 'magnemite': [], 'marowak': ['dratini', 'porygon', 'kabutops', 'goldeen'], 'pidgey': [], 'dragonair': [], 'poliwag': [], 'magikarp': ['articuno', 'kabutops', 'lapras', 'mew'], 'fearow': ['omastar'], 'slowpoke': ['koffing', 'farfetchd', 'hypno', 'krabby', 'gengar'], 'starmie': ['dragonite', 'magikarp', 'scyther'], 'ekans': ['slowbro', 'paras', 'electrode', 'rapidash'], 'meowth': ['dodrio', 'poliwrath', 'ditto', 'tentacool', 'aerodactyl'], 'raichu': [], 'kabuto': ['aerodactyl', 'articuno', 'kabutops'], 'charizard': [], 'oddish': ['flareon', 'horsea', 'drowzee', 'tauros'], 'wigglytuff': ['dragonite', 'oddish'], 'pidgeot': ['seel', 'bellsprout'], 'hitmonlee': ['seaking', 'mew', 'gyarados'], 'charmander': [], 'mewtwo': ['mew'], 'bellsprout': ['tauros', 'gengar', 'electabuzz', 'ponyta'], 'hypno': ['flareon'], 'kadabra': [], 'nidoking': ['venonat', 'muk', 'farfetchd', 'zubat', 'articuno'], 'sandslash': ['gyarados', 'golbat', 'alakazam', 'mewtwo', 'poliwrath'], 'diglett': ['graveler'], 'ditto': ['kabuto', 'vaporeon', 'aerodactyl'], 'arbok': ['horsea', 'primeape', 'hitmonlee'], 'abra': ['grimer', 'tangela', 'dragonite'], 'jigglypuff': [], 'tentacool': ['weezing', 'mewtwo', 'farfetchd', 'moltres', 'grimer'], 'tentacruel': ['dodrio'], 'tauros': ['flareon', 'moltres', 'porygon', 'omanyte'], 'dodrio': [], 'exeggcute': [], 'victreebel': ['tentacruel', 'seaking', 'ditto', 'lapras'], 'nidoranfemale': ['jynx', 'persian', 'shellder', 'mewtwo'], 'shellder': ['vaporeon', 'marowak', 'articuno', 'tauros', 'gyarados'], 'nidorino': ['omanyte', 'gastly', 'magneton', 'marowak', 'paras'], 'aerodactyl': ['zapdos'], 'kingler': ['mew', 'cubone', 'mr.mime', 'dratini', 'weezing'], 'seadra': ['mr.mime', 'scyther', 'jynx', 'electabuzz', 'magmar'], 'exeggutor': ['mr.mime', 'dragonite', 'hitmonchan', 'flareon', 'gyarados'], 'koffing': ['weezing', 'chansey', 'omastar'], 'farfetchd': ['rhyhorn', 'cloyster', 'moltres', 'vaporeon', 'dodrio'], 'jolteon': ['kabutops', 'snorlax', 'omastar', 'aerodactyl'], 'sandshrew': ['lickitung', 'nidoranmale', 'clefairy'], 'magmar': ['snorlax', 'tauros', 'pinsir', 'lapras'], 'electrode': ['lapras', 'staryu', 'seaking', 'marowak', 'horsea'], 'dratini': [], 'mankey': ['farfetchd', 'electrode'], 'magneton': ['mr.mime', 'kabutops'], 'staryu': ['ditto', 'dratini'], 'seaking': ['staryu', 'magikarp', 'starmie', 'dragonite'], 'caterpie': ['weedle', 'vulpix', 'shellder', 'moltres'], 'blastoise': ['electrode', 'vileplume', 'gastly', 'goldeen', 'sandslash'], 'pidgeotto': ['lickitung', 'spearow'], 'pikachu': ['hitmonlee'], 'weepinbell': [], 'gastly': ['seadra', 'mew', 'rhydon', 'horsea', 'tangela'], 'scyther': ['jynx', 'articuno', 'mew'], 'porygon': ['aerodactyl', 'mewtwo', 'kabuto'], 'poliwrath': ['machop', 'victreebel', 'seel', 'gengar', 'vaporeon'], 'dragonite': ['mewtwo', 'mew'], 'geodude': ['magneton', 'seel', 'cubone'], 'hitmonchan': [], 'lickitung': [], 'eevee': ['articuno', 'jolteon', 'flareon'], 'venomoth': [], 'moltres': ['dragonair'], 'metapod': [], 'horsea': ['moltres'], 'graveler': ['seaking', 'tangela', 'slowpoke'], 'kangaskhan': ['dragonite', 'kabuto', 'zapdos', 'moltres'], 'cloyster': ['mr.mime', 'marowak', 'kabutops', 'gengar', 'eevee'], 'machop': ['staryu', 'machamp', 'slowpoke', 'dodrio'], 'kakuna': ['scyther', 'zubat'], 'voltorb': ['porygon', 'pinsir', 'dragonite', 'jolteon', 'moltres'], 'ninetales': ['farfetchd', 'parasect', 'ponyta', 'mewtwo'], 'machamp': ['onix', 'marowak'], 'jynx': ['dratini', 'tauros', 'snorlax'], 'seel': ['haunter', 'kangaskhan'], 'dewgong': ['hitmonchan', 'pinsir', 'eevee'], 'growlithe': ['kabutops', 'shellder', 'farfetchd', 'chansey'], 'vaporeon': ['porygon', 'jolteon', 'aerodactyl'], 'haunter': ['koffing', 'rhyhorn', 'aerodactyl'], 'nidorina': [], 'alakazam': ['krabby', 'machoke', 'tauros', 'horsea'], 'venonat': ['magmar', 'drowzee'], 'nidoranmale': [], 'omastar': [], 'golbat': ['scyther', 'parasect', 'oddish'], 'parasect': ['persian', 'electabuzz'], 'squirtle': [], 'drowzee': [], 'chansey': ['pinsir', 'vaporeon'], 'slowbro': [], 'rhyhorn': ['staryu'], 'clefable': ['golbat', 'ditto'], 'goldeen': ['magikarp'], 'zubat': ['eevee', 'gyarados', 'dodrio', 'seadra'], 'doduo': ['shellder'], 'lapras': ['omanyte', 'omastar', 'mewtwo'], 'persian': ['golduck'], 'psyduck': ['abra'], }