Recursion

       Recursion is a very powerful tool we can access in Python. Actually, most of programming languages support recursion, which shows the importance of recursion in the field of computer science programming. In real life, a lot of problems is much easier after we break them into pieces, then solve those subproblems one by one. Recursion can help us to do that when we code.

       In general, Recursion means "defining something in terms of itself", and in Python, we call the function again inside of that function. However, in order for a recursive function process properly, it has to have at least one base case and at least one general case.

       A general case is where we call the function itself using recursion. Sometimes, we may need to update the input for general cases every time it recurs according to the function requirement. A recursive function may need to call itself a lot of time in order to achieve the optimal goal, but it surely would make the problem a lot easier than solving the problem as a whole. On the other hand, a base case is a restriction to this recursive function. It is defined to stop recursion when it is necessary. Otherwise, the function will call itself until our computer run out of memories or raise an error in some situations.

       An simple example for recursion would be nested_list_max, which finds and returns the maximum integer in a nested list:

                     def nested_list_max(L: list) -> int:

                            """Return the maximum in nested list L.

                            """

                            return max([nested_list_max(i) if isinstance(i, list) else i for i in L])

This function will form a list using list comprehension: it goes into every item in list L, if the that item is a integer, it will add it into the list; if the item is a list, the function will call itself again on that item. After the function goes through every item in list L, it will find the maximum number in the list that made by list comprehension. No matter what is the depth of the list L, the function will always go thought every element in it.

       In the above problem, it looks pretty simple. But if we want to code it without recursion, it would be really hard, since we need to consider the depth of the input list L. Once again, it is really important to have a base case and a general case. In the example, my base case is that if item i is not a list, the list comprehension would add i into the new list. And my general case is that if i is a list, the list comprehension would add the result of nested_list_max into the new list.

      Recursion can do a lot more than the example I showed, and there is still a lot of things I need to learn about it. Once I can ace recursion, I believe coding would be a lot easier in the future.

Week 6: Recursion Structure - Tree

       After learning how to code recursion, we learned about tree, a recursion structure, this week. It took me some time to get used to the traversals: pre-order, in-order, and post-order. It become much easier once I understood the recursion within them. For pre-order, we just need to visit root first, then pre-order (recursion) left subtree, then pre-order (recursion) right subtree. So, if left/right subtree is a leaf, then we can just return that node. If the subtree is a internal node, then we treat the subtree as a new tree, and analysis it again. In-order and post-order is very similar to pre-order. The difference is that they visit root, left-subtree, and right-subtree in different orders.

       After that, we start to learn about the coding for those traversals, but it was kind of confusing. It was quiet amazing for the code to be so short for such complicated tasks. I thought I got the code after some discussion with classmates. In this week's lab, there is a similar problem. I tried solve it in one line, but the only thing I got is a headache. On the other hand, my partner combined the use of list comprehension and ternary, and coded it in one line. That was exactly what professor told us during lecture. But I did not know how to use them properly. Hence, my plan for the reading week is to ace recursion, list comprehension, and ternary, as well as getting ready for our mid-term test.

Week 5 Learning Recursion

       Continue from last week's lectures, recursion is still the top topic in this week. I did more practice on tracing recursion, and learned how to code recursions. When professor talked about tracing during lectures, he also told us how to be lazy. Never trace something we know what its output is. It will save us plenty of time.

       In lectures, an example about coding for recursion is the Tower of Hanoi. It was quite easy to code it, because I knew how to play the game, and professor gave the step-to-step instruction on it. Besides, professor finished the base case for this recursion. It makes the lecture seems really easy.

       However, I got a lot problems when I wrote the code for the recursion in assignment one, since nobody gave me the base case or general case or step-to-step instructions about it this time. I failed couple times, because I forgot to write code for the base case. So my recursion just kept repeating until I found this mistake out.

       I think I would still take a long time before I can ace recursion in test.

Week 4: Practices on subclasses, errors, unittests

    Even though recursion was the main topic in lectures, I have to say that I learned something more from lab and exercise this week. During the lab, my task is to create some classes and subclasses, then finish up with some unittests for each class. The part of creating classes and subclasses was not very hard. The hard part for me is to create unittests, because my partner and I did not get any practice on it. Only thing we know is that we need to use assert to find out if actual is the same as expect. We had no clue what module should be imported, what superclass we should use, and what code we should put under if __name__ == '__main__'. After some researches, we figured out the necessary codes:

              import unittest

              import OurModuleName

              class TestOurModule(unittest.TestCase):

Then we created several proper test cases by using assert. At the end of file, we put:

              if __name__ == "__main__":

                     unittest.main(exit=False)

       On the other hand, I got more experienced about raising errors in this week's exercise. The exercise is quite simple, but I spent a lot time on it, since I had very limited knowledge about errors. After reviewing professor's notes, and reading information on websites. I successfully used try, and except to catch and process errors, while I used raise to produce a error.

       Since I mainly focused on unittests, subclasses, and errors this week, my goal for next week would be doing more practice on recursion, and master recursion.