Week 7: More on recursion

  In our assignment 2 , when we use Minimax Strategy, we actually applied a recursion of one kind of tree structure, and to be honest, it is an easy one.

  In our lab06, we were asked to do some exercise due to recursion, which were fairly interesting. For example, the part of implementing parenthesize, it is another form of calculator in comparison with RPN calculator I have done in week 5's SLOG.

 if isinstance(b.data, float):
        return str(b.data)
    else:
        return "(" + parenthesize(b.left) + b.data + parenthesize(b.right) +")"

And the following is the code for list_between, which is used to return a list of
integer of tree value lies between the interval.

    if node == None:
        return []
    elif start <= node.data <=end and is_leaf(node):
        return [node.data]
    else:
        if node.data < start:
            return list_between(node.right,start,end)
        elif node.data > end:
            return list_between(node.left,start,end)
        else:
            return list_between(node.left,start,end)+[node.data]+list_between(node.right,start,end)

The idea is that instead of traversing the whole tree, we construct a base case in which we know we can return "something", and then we just need to think like an idiot who asks only his neighbors what value to return without looking ahead.
In this case, in order to avoid "unnecessary" process of recursion, we can add some if statement to decide whether we need to look up for current node's all children. For example, if the data of current node is less than the start, we don't need to look up for its left child given its an well ordered binary tree. Similarly, we don't need to look up for its right child if its data bigger than the end. At last, if the data is inclusively between the start and the end, we add its data up with values returned from its left child and right child for which we both use list_between method in order to get recursive result.