Week 7

This week I'm going to write something about recursion.  Professor Heap mentioned this topic in the first week of class.  It sounded totally fresh to me, but after these weeks of learning and practice, recursion no longer sounds so intimidating.  In CS context, recursion is defined as the approach to solve a problem by having 'functions to call themselves to solve smaller subproblems'.  Based on my understanding, recursion involves writing the code for a function with use of the function itself.  It helps avoid redundant code so that sometimes we can simply write a neat one-line return statement for a complicated function.

The first function that we touched upon was 'sum_list' that sums up all the values in a nested list.  Without recursion, we would have to write similar code to take the sum of each sublist in the nested list.  With the use of recursion, and help of tenary if and list comprehension, we were able to write the function in one line: return sum([sum_list(x) if isinstance(x, list) else x for x in L]).  See that the function 'sum_list' itself appears in this return statement, so that the function is executed for each nested list recursively.  In the beginning, it was a little bit challenging to understand recursion so I practiced tracing the function for many times to get comfortable with this approach.

Then we got to see a lot of examples, such as finding the depth of a nested list and maximum in nested list.  We also got to practice quite a lot problems in the lab.  After doing recursion over and over again, I eventually figured out my own efficient way of writing recursion codes.  First, I carefully read the description of the function (what it is trying to do).  Secondly, I list out different situations and organize them into 'if' statements.  Then I check which situations need to call the function itself.  Finally I re-organize and put them into a simple return statement.  

I think the hardest part is usually not to figure out where to use recursion, but to put all conditions together and make the code concise.  For example, the code for nested depth of list was return (1 + max([nested_depth(x) for x in L] + [0]) if isinstance(L, list) else 0).  It is very easy to mess up the '[]' and '()', and where to put the add 1.  Also, the '+[0]' might easily be ignored because it only serves the special case of an empty list.  Here, the case of a non-list is called the base-case where no recursion is executed. 

Moreover, we practiced recursion in Assignment 1.  In the tour.py, recursion was so vital to record the series of moves.  It was such a good practice for me since it integrated different approaches.