Week 9: Optimizing Recursion

Thus far in CS148, we have learned that while recursive functions are often more elegant than functions that use loops, they are often not as efficient. However, there are ways of optimizing recursive functions.

For example, in a recursive function on a tree, you can choose to ignore branches of the tree that will not impact the output of your function. This reduces the number of recursive calls you make on your tree, and optimize the efficiency of the function.

        

    # The optimization here is that you can ignore branches. So you add conditions to IGNORE them.

    # When do you ignore the left branch? When node.data < start.

    # When node.data < start then you ignore the left branch.

    # See below:

    

    def list_between(node, start, end):

    ''' (BTNode, object, object) -> list

    

    Return a Python list of all values in the binary search tree

    rooted at node that are between start and end (inclusive).

    

    >>> b = BTNode(8)

    >>> b = insert(b, 4)

    >>> b = insert(b, 2)

    >>> b = insert(b, 6)

    >>> b = insert(b, 12)

    >>> b = insert(b, 14)

    >>> b = insert(b, 10)

    >>> list_between(None, 0, 15)

    []

    >>> list_between(b, 2, 3)

    [2]

    >>> L = list_between(b, 3, 11)

    >>> L.sort()

    >>> L

    [4, 6, 8, 10]

    '''

    if node is None:
        return []
    else:
        left_list = (list_between(node.left, start, end) 
                     if node.data > start 
                     else [])
        right_list = (list_between(node.right, start, end) 
                      if node.data < end 
                      else [])
        node_list = ([node.data] 
                     if (start <= node.data <= end) 
                     else [])
        return left_list + node_list + right_list