Week 7: Recursion

    We have been working with recursion since the fourth week of this course on lectures, labs, exercises and assignments. Here I will write down some usage of recursion including some examples which I encounter during my study. Even now, I cannot confidently say I have master all the ideas of recursion, but at least part of it. Write down them and remind myself in the future.
    The basic idea of recursion is that we define a base case for a function, then step one by one. We get any of what we want. To write a recursive function, the very first thing is to think about the base case. Sometimes the base case may not be written individually, but more time we will write them explicitly. Next is the recursive step. What we will do is just assume we are done with the function and it is definitely correct, and then try to get the production.
    Here for some examples.
   

    This example is from the lecture and it was my first time to feel the power of recursion when encountering it. It returns the depth of a nested list. It seems difficult to tackle this problem. But if we assume we have done the function and things get much simple. For base case, when L is not a list, it should return 0. And then we use a list comprehension and built-in function 'max' to get the maximum depth of each element in L. Plus one and get the result. It is not hard when we look back.
    Next example:

    This function is trying to get the height of a Tree. Tree is a newly kown data structure. Using recursion to deal with Tree problems is quite helpful.
    In additon, Assignment 1 uses a lot of recursion. Also some examples in the reading materials.
http://openbookproject.net/thinkcs/python/english3e/recursion.html .They may be helpful in the future.
    In week 7's lab, we use recursion to write some methods of linked list ADT.