Week 7 - RECURSION

RECURSION

Recursion is a way of defining a functions in which the function is applied in its own definition. It is one of the main ideas of Computer Science. A common thing done when writing code is to divide the problem into smaller problems and then combine the results. It is mostly used when the problem can not be solved by a for or while loop for example, checking elements in an arbitrarily nested list. One exercise we did in lecture was tracing this code:

def sum_list(L):

    """ (arbitrarily nested list of int or int) -> int 

    Return the sum of all ints in L. 

    >>> sum_list([1, [2, 3], [4, 5, [6, 7], 8]]) 

    36 

    """ 

    if isinstance(L, list): 

        return sum([sum_list(x) for x in L]) 

    else: 

        return L  

In the code above, the function sum_list is calling itself inside its own definition. It keeps on looking inside the nested lists until there are no lists left and returns the sum in the end. There are three helper functions used in this code, sum, isinstance and sum_list. Our base case is when L is an integer, we do not need recursion for this. So, when the function is called on an integer, it will the integer. For example, sum_list(25), L is not a list, so the if condition is false and it returns L which is 25 in this case. Here, recursion is needed when calling the function on nested lists. For example,

sum_list([4, [1, 3, 5], 9]) -> sum([sum_list(4), sum_list(1, 3, 5), sum_list(9)])

                                      -> sum([4, sum(sum_list(1), sum_list(3), sum_list(5)), 9])

                                      -> sum([4, 9, 9])

                                      -> 22

The function calls itself on each list. This is how recursion works.

                          

Week 6

This week we got our term tests back, I did not do very well but I am happy that I passed. This week we started a new concept of trees. A tree is a set of nodes with directed edges between some pairs of nodes. The edges connect the parent nodes and the child nodes, each node has exactly one parent. Trees can basically be used to represent hierarchical relationships, for example, inheritance in a program. Another cool thing we learned was ternary if. We can write long if statements in one line now. We wrote some code for the tree, at first I was quite confused but later when I read it thoroughly I kind of understood the concept. We also did a worksheet in class which had different questions about trees. This week's lab was also based on trees, we had to write some methods for it. The quiz in the end was also about the same topic, I feel I understood the concept more after the lab that's why I was able to easily answer the questions on the quiz. Finally, next week is reading week, I will get some time off to relax and take my mind off the hectic schedule. But, I am not going to miss this opportunity to catch on topics that I don't understand very well like stacks and queues. So, I'm going to take 2 or 3 days off and then start studying.

Object Oriented Programming

Object oriented programming (OOP), as the name suggests, programming based on 'objects', these objects are data structures. OOP contains methods such as inheritance. Inheritance is a method used when creating different classes, it is when a class is based on another  class. There are child classes and parent classes, the child class inherits all the methods and functions from the parent class. In CSC108, we did not see this as much but in this course we have only been working with classes and its methods and so I am quite familiar with this method. Inheritance is very useful since it helps in avoiding repetitive code. Classes contain other methods as well, such as __init__ which is used to initialize an object in the class, __eq__ which is used to compare two objects, __str__ for a string representation of the object and __repr__ for a formal representation of the object.

Week 5

This week we had our first term test on Wednesday, the test wasn't so difficult but unfortunately I had my MAT137 test on the same day so I couldn't prepare for the term test very well. On Monday there was a snow storm which is why I was not able to attend the class and in our Wednesday lecture time slot we had our term test. From what I understood from lecture's codes posted on the course website, the prof talked about test cases in unittest. She had a code according to which they implemented some test cases. Another thing discussed in class was a 'bracket balancer' code, this code returned whether the given line had balanced brackets i.e. same brackets on both ends of the line. This function basically looks like it's written to ensure that none of the brackets in a line or an equation are missed out. This week's lab was about stacks and queues, and for the first time ever since labs started I was able to finish the lab exercises on time. This week's quiz was also based on queues so it wasn't so difficult.

Recursion

Last week we started learning about recursion. I feel one of the main ideas in Computer Science is recursion. Recursion is basically a method where the solution of a problem depends on smaller instances of the same problem. Recursion is very useful, big problems can efficiently be solved by dividing the problem into smaller versions and then combine the results to get the solution to the big problem. Recursion actually helps in saving up so many lines of code. Recursion is so far my favourite topic. Although sometimes it does get quite hard to trace the code but it is an extremely useful thing. A code with recursion looks beautiful but it is hard to understand at first.