CODEWITHSUNDEEP
pythondictionaryrecursionbinary-tree
Naeem Ahmed
Naeem Ahmed

Reputation: 105

Return dictionary from recursive function

I have a binary search tree where each node represents a game length. I have to return a dictionary where the key is the length of the game and the value is the number of games that are of that length. The recursion call goes through every node in the tree but it returns an incorrect dictionary. I'm positive that the problem is how I'm returning the dictionary. Any help will be appreciated 

game_len = {}
if not node.children:
    key = len(node.possible_next_moves())
    if key not in game_len:
        game_len[key] = 1
    else:
        game_len[key] += 1
else:
    key = len(node.possible_next_moves())
    if key not in game_len:
        game_len[key] = 1
    else:
        game_len[key] += 1
    [game_lengths(child) for child in node.children] 
return game_len

Upvotes: 2

Views: 3295

Answers (1)

Blckknght
Blckknght

Reputation: 104712

In general, there are two ways to handle the return values from a recursive algorithm. Either you can collect the return values from your recursive calls and combine them, or you can pass in an extra mutable argument which the recursive calls can modify. I think the latter is likely to be best in this situation, since dictionaries are easy to mutate in place but not especially easy to merge together:

def game_lengths(node, result=None):
    if result is None:
        result = {}

    #... add a value to the result dict, handle base cases, etc.

    for child in node.children:
        game_lengths(child, result)

    return result

Upvotes: 6

Related Questions