Recursion is a must-know strategy in applied programming since many problems in biology, especially ones to do with trees, can only be solved this way. The problems that lend themselves to a recursive solution are the ones that can be broken into two or more sub-problems of the same type (recursive case), until these become simple enough to be solved directly (base case). The solutions to the sub-problems are then combined to give a solution to the original problem.
To help you on your way here is an example from the lecture. The function sumList(lst) sums the elements of the list lst recursively. Notice that we test whether each recursive call to the function should consider the base case or the recursive case:
def sumList(lst): if len(lst) == 1: # base case return lst[0] else: # recursive case return lst[0] + sumList(lst[1:])
But on to trees, which is where recursion becomes really handy. To remind you of how a tree is represented in this manner, here is a figure from the lecture that shows a tree and the corresponding tuple representation. Remember that each tuple is a tree in its own right. The entire outer tuple represents the entire tree and the members of this outer tuple are the trees that this entire tree is made up of. By looping over the elements of a tuple (with a for loop) you iterate over the next level of sub-trees or leaves that make up the tree that this tuple represents. Here is a function countLeaves(tree) that counts the leaves on the tree tree.
def countLeaves(tree): c = 0 for i in range(len(tree)): if type(tree[i]) is not tuple: c += 1 else: c += countLeaves(tree[i]) return c
Exercise
Write a function sumLeaves(tree) that takes a tree tree, in the form of nested nested tuples. The leaves of the tree are integers and the function should return the sum of all these leaf integers.
Example usage:
tree = (((1, 2),(3, 4)),((5, 6),7))
print sumLeaves(tree)
28