Tracing Recursion

This week I have to write my impressions on tracing recursion from week 4. I found tracing recursion quite simple and straightforward. When tracing recursive functions, I think it is important to start by identifying the base case because that is most likely the easiest case. Then, I would identify the general case. The thing about the general case is, you have to think about it in terms of the base case because after tracing the general case, it will eventually lead you back to the base case.

For example:

def count_elements(L):
    ’’’(list or non-list) -> int
    Return 1 if L is a non-list, or number of non-list elements in
    possibly-nested list L.
    Assume: L is any Python object.
    # examples omitted!
    ’’
    if isinstance(L, list):
        return sum([count_elements(x) for x in L])
    else: # if L is not a list, count it
        return 1

In this example, return 1 when the input is not a list is the base case. The general case is return the sum of the list after it has been passed by count_elements. The general case passes the list into count_elements into there are not more lists within the list. When this happens, we return a 1 using the base case.

That is basically all I have to say about tracing recursion. We also wrote the first midterm of the year for this class this week. I thought it went pretty well. It was pretty much what I expected, decently difficult questions that reflect what you have encountered in lecture and in labs.

Thanks,

J.M.