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.
