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