Week 11 Recursion Review

By the assignment 3, I have more understand about Recursion:
1. For some functions, it seems like that recursion cannot apply on it, but I can develop a helper function with a recursion to help me to solve the problem. For example:

def distinct_node_count(root):
    '''(GameStateNode) -> int
   
    Return the number of nodes representing distinct game states in the
    tree rooted at root.  Two game states are distinct if they are not __eq__.
   
    >>> s = SubtractSquareState('p1', current_total = 6)
    >>> root = GameStateNode(s)
    >>> root.grow()
    >>> distinct_node_count(root)
    10
    '''
This function have to return a int which cannot hold information about abstract object "GameStateNode" so recursion is not applicable; however, I can design a helper function which return a set to contain the data then recursion is applicable:

def distinct_node_set(root):
    '''(GameStateNode) -> set
   
    Return a set of all distinct nodes.
    '''
    if root.children == []:
        s = set()
        s.add(repr(root.value))
        return s
    else:
        result = set()
        result.add(repr(root.value))
        for r in root.children:
            for n in distinct_node_set(r):
                if n not in result:
                    result.add(n)
        return result

After that, the only thing I need to do is count the length of my set:  

def distinct_node_count(root):
    '''(GameStateNode) -> int
   
    Return the number of nodes representing distinct game states in the
    tree rooted at root.  Two game states are distinct if they are not __eq__.
   
    >>> s = SubtractSquareState('p1', current_total = 6)
    >>> root = GameStateNode(s)
    >>> root.grow()
    >>> distinct_node_count(root)
    10
    '''
    return len(distinct_node_set(root))

2. Another interesting thing is that we can use dictionary in recursion. Recursive function can help us to accumulate values of each key:

def branching_stats(root):
    ''' (GameStateNode) -> {int: int}
   
    Return a dict that represents the distribution of branching factors in
    the tree rooted at root. Each key is a branching factor >= 0, and its
    value is the number of nodes with that branching factor.
   
    >>> s = SubtractSquareState('p1', current_total = 6)
    >>> root = GameStateNode(s)
    >>> root.grow()
    >>> branching_stats(root) == {0: 4, 1: 6, 2: 3}
    True
    '''
    if root.children == []:
        return {0: 1}
    else:
        result = {}
        result[len(root.children)] = 1
        for r in root.children:
            for k in branching_stats(r).keys():
                if k not in result:
                    result[k] = branching_stats(r)[k]
                else:
                    result[k] += branching_stats(r)[k]
        return result

If the key exists in my dictionary, I just need to add the value by 1. If the key is not in the dictionary yet, I will create it and let its value equal to 1. After all, I can get a complete dictionary of the branch counting of my tree.

There is a similar function, but instead of the dictionary, it creates a list of string:

def game_descriptions(root):
    ''' (GameStateNode) -> list of str
   
    Return a list containing a str describing each complete game that is
    possible from the game stored at root.
   
    Assume root is the root of a game state tree specifically for the game
    Subtract Square.
   
    >>> s = SubtractSquareState('p1', current_total = 6)
    >>> root = GameStateNode(s)
    >>> root.grow()
    >>> game_descriptions(root)
    ['p1:6 -> p2:2 -> p1:1 -> p2:0 = p1 wins!', 'p1:6 -> p2:5 -> p1:1 -> p2:0 = p1 wins!', 'p1:6 -> p2:5 -> p1:4 -> p2:0 = p1 wins!', 'p1:6 -> p2:5 -> p1:4 -> p2:3 -> p1:2 -> p2:1 -> p1:0 = p2 wins!']
    '''
    if root.children == []:
        if root.value.winner('p1'):
            return ['p2:0 = p1 wins!']
        elif root.value.winner('p2'):
            return ['p1:0 = p2 wins!']
    else:
        v = abbreviated(root.value) + ' -> '
        result = []
        for c in root.children:
            for d in game_descriptions(c):
                result.append(v + d)
        return result

At first, I have to decide what kind of the string should be printed for the end, then I add the other parts at front one by one.

Assignment 3 is a good practice of recursion. It shows me more ways to use recursion to solve complicate problems. I think it is a good preparation for final exam.