Sunday, March 1, 2015

Week 7: Summary on Recursion

    In the beginning, the class started with recursion examples that were fairly simple and easy to trace, for the purpose of understanding the concept of recursion. I noticed that most of the earlier examples of recursion dealt with list depth, and that if a function's input was a deeper list, it was harder to keep track of the recursion in my head, but tracing it on paper was much easier. So I learned that one way of using recursion was first utilizing isinstance to check if an object's type was a list, and using recursion to perhaps build a list (to return the largest or smallest instance for example) or keep count of a specific instance in L (such that L is the input of the function).
An example from January 26th's nested list examples:

if isinstance(L, list): #where isinstance checks if the type object of L is a list
    return max([rec_max(x) for x in L])
 else: # L is not a list
    return L

    Also, an else statement is placed at the end of the body to act as an alternative in such a case where L is not a list. The function of this statement largely depends on the beginning if statement and description of function.

    Unfortunately, the class recently analyzed more difficult recursion techniques involving trees, including binary trees and binary search trees. An additional feature of these trees is that there are parts of the tree called leafs, nodes and children which we can use recursion on to evaluate all nodes or specific nodes. What makes binary trees special is that they are limited to 2 children per node and what makes binary search trees special is that they are also limited to 2 children per node, but the left child is lesser than the parent and the right child is greater than the parent. These characteristics are essential to how we utilize recursion regarding trees. The standard procedure in creating code for these trees is to first write an if statement that accounts for the simplest case in which recursion is not needed. Often this case is when the tree does not exist or there are no children, simply one node, and therefore, something is returned immediately before any recursion is necessary. Secondly, an else statement is created to account for cases in which recursion is needed. An example of this would be the evaluate function from February 23rd's evaluate exercise:

if b.left is None and b.right is None: #if b has no children, return b.data
    return b.data
else: # if b has children, use recursion to evaluate the proper expression
    return eval(str(evaluate(b.left)) + b.data + str(evaluate(b.right))) 
#here, evaluate(b.left) and evaluate(b.left) must be strings for eval to work, hence why str must be used

As a side note, binary trees often use eval which is a built-in function that runs python code in a string within itself, and evaluate to evaluate the expression rooted at b.





No comments:

Post a Comment