Week 7, Recursion Recursion!

Unlike usual post, this slog will be all about the assigned topic "recursion".

So what is recursion? it basically is a process of repeatedly breaking the bigger problem- which is either hard or seem like impossible to solve - to smaller problem which is easier to solve. It's more or less like the poof technique that i learnt in CSC165 called 'induction'. But in recursion, rather than proving the basis step, i have to find the solution to base case (often known as basis step of a recursive function). And according to blog.ezyang.com, i can use induction to prove whether my recursive function is correct since inductive hypothesis in induction behaves like recursive call in recursion! Which sounds very interesting but the prof didn't mention about it in CSC165, may be it was too advanced for the first year.

A question came to my mind when i first made a recursive function 7 weeks ago is that, "why do i have to make a recursive function while i can use 'for' or even 'while' loop to solve the problem". And after working through all of the exercises, term test and especially the assignment 1, i got pretty good ideas why do we need recursive function. 

Let consider an example:

def slog_example1(list1): # without using recursion
    """(list of int) --> int
    return sum of list1 which has max list depth of 3.
 
    >>> slog_example1([1,[2, 3, [4, 5], 1]])
    16
 
    """
    total = 0
    for i in list1: # 1 time
        if isinstance(i, int):
            total += i
        elif isinstance(i, list):
            for i in i: # repeat 2nd time
                if isinstance(i, int):
                    total += i
                elif isinstance(i, list):
                    for i in i: # repeat 3rd time
                        total += i
    return total

def slog_example2(list2):
    """(list of int) --> int
    return sum of list2 which has unlimited list depth.
 
    >>> slog_example2([1,[2, 3, [4, 5], 1]])
    16
    >>> slog_example2([[[[[[[[[[[[1]]]]]]]]]]],1])
    2
    """
    if isinstance(list2, list):
        return sum([slog_example2(n) for n in list2])
    else:
        return list2 

Two functions slog_example1 and slog_example2 are both performing the same task which is calculating the sum of integer elements inside the nested list. The recursive function slog_example2 can calculate the sum of integer within the list of any depth(max: 979 - check out my first extra post), whereas the maximum list depth that can be afforded by the iterative function slog_example1 is only 3 since i only repeated my 'for' loop 3 times. So unless i am patient enough to retype the 4 lines within my 'for' loop 980 times- which is rather a crazy thing to do, i would refer to use the recursive function slog_example2 to solve the problem! Imagining that if the same problem is given in the exam with infinite list depth which method should you choose?

So, the first obvious advantage of recursion over iteration is that it turns a problem that seems impossible into a possible problem. But now let consider another version of slog_example2:

def slog_example2v2(list2):
    """(list of int) --> int
    return sum of list2 which has unlimited list depth.
    >>> slog_example2v2([[[[[[[[[[[[1]]]]]]]]]]],1])
    2
    """
    return sum([ n if isinstance(n, int) else slog_example2v2(n) for n in list2])

That is the beauty of list comprehension that allows me to turn 980x4 lines of iterative code into 1 single line of recursive code. Recursion together with list comprehension not just make the code look elegant but save programmer's time and possibly money. Moreover, in some case, the recursive solution is even more understandable than the iterative solution since a recursive solution is usually very short, typically from 1 to 10 lines.

We now look at the time complexity of those three function. If you copy and run the following code in your python, you would be able to figure out which one of the iterative, recursive or list comprehension+recursive take longest and shortest time to process (check out my second extra post):

import time
def time_test():
    start = time.time()
    slog_example1([1,[2, 3, [4, 5], 1]])
    a = time.time()-start
    print('iteration takes: ' + str(time.time()-start) + ' to run')
    start = time.time()
    slog_example2([1,[2, 3, [4, 5], 1]])
    b = time.time()-start
    print('recursion takes: ' + str(time.time()-start) + ' to run')
    start = time.time()
    slog_example2v2([1,[2, 3, [4, 5], 1]])
    c = time.time()-start
    print('list comprehension + recursion takes : ' + str(time.time()-start) + ' to run')
    dict_time = {'iteration': a, 'recursion': b, 'lc+rec': c}
    print('longest time: ', max(dict_time, key = dict_time.get)) # return the method that takes longest time
    print('shortest time: ', min(dict_time, key = dict_time.get)) # return the method that takes shortest time

The result is that for  a nested list of any depth and at any length, the recursive code (without list comprehension) always take longest time to process, whereas, the iterative code though is longer take least amount of time. So i can conclude, although a recursive solution is generally very short, it is not necessary that it takes less time than an equivalently lengthly iterative solution. Time complexity therefore is the biggest disadvantage of using recursion (at least in the programming language like Python).

My last point is about debugging, in my own experience, it is much harder to debug a recursive function since it requires me to keep track of the whole stack consisting the results to many smaller problems not just the variables like in iterative function. 

Week 6 Tired!

Yes, i got very tired week! It was not because of CSC148 first assignment which i already finished last week, it was all of the quizzes, midterms, assignments from other courses, that drove me crazy. Moreover, when i checked my A1 file yesterday night, i realized that the TA only gave me 1 out of 4 for my Slog, they said that i missed the post on Object Orientated Programming (Week3) but it was right there, so i submitted a remark file on Markus and hopefully that one of TAs will check it out and remark my Slog.

During the lecture this week, we were introduced "Tree" which is a very common data structure in any programming languages. We talked about different terminologies used in Tree data structure, such as parent, children, node, root, leaf, edge ... which are fairly interesting and understandable. However, when the professor implement Tree in Python, i was kind of lost! Not only me, but my partner who sat next to me also had no idea. I am little bit worry about it now since the mid-term is coming soon in less than two weeks. Luckily, i have 9 days off from school, so i definitely will go over all of the course's material and hopefully be ready for the midterm before the class start again.

The practical tasks for this week was really interesting. We were asked to rewrite 4 functions , but instead of using list comprehension like in the sample codes, we had to write the codes in the traditional line-by-line form. I learnt how to use some of the very useful Python built-in functions such as any() and zip(). I especially like zip(), it is extremely useful and efficient when i have to iterate over several lists. Below are some of the common uses of zip():

Example1: Turning column into row! In MAT223 midterm that i sat about 6 hours ago, one of the easiest question was to find the transpose of the matrix ([1, 2, 3], [2, 4, 5], [1, 3, 2])! So i developed a program to solve the question.

def transpose():
    Row1 = [1, 2, 3]
    Row2 = [2, 4, 5]
    Row3 = [1, 3, 2]
    Matrix = [Row1, Row2, Row3]
    Matrix_inverse = []
    for d,e,f in zip(Row1, Row2, Row3):
        Matrix_inverse.append([d, e, f])  # the rows now are turned into columns.
    print(Matrix_inverse)

Example2: Turning 2 corresponding list into dictionary with key and value.

def transfer(instructor_list, course_list):
    '''
    >>> transfer(['Paul', 'Tom'], ['CSC108H1', 'CSC165H1'])
    {'Paul' : 'CSC108H1', 'Tom': 'CSC165H1'}
    '''
    return dict(zip(instructor_list, course_list)) # return a dictionary with names of the instructors as the #keys and the corresponding course that they are teaching as the values.


That is, that are all that i want to share for this week! Over the reading week, i will make some extra posts when going over the course material!

As usual, I would like to give my-self a grade of for my overall learning experience! 3/5 seems to be a reasonable grade, since i yet have a completed understanding about "Tree" data structure.

Week 5

Hello every one, normally i wrote my blog at the beginning of the weeks but i changed my mind this time, writing it on Friday because i want to share with you guides some of my thought after working through all of the tasks in the Assignment 1. I expected that the first CSC 148 assignment would be very easy ! (as i already experienced the easiness of the 1st CSC 108 assignment) . Unfortunately, my thought was wrong. I planned to complete the assignment over the weekended, but until today ( Friday), i still can't figure out what to do with the bonus question and moreover i yet completed any of the docstrings for the function that i wrote. In detail, i don't really understand the difference between the 2 methods TOAHModel._eq_ and TOAHModel.same_strategy. I think that the docstring descriptions of these two methods are little bit vague, so i did make a question in Piazza and hopefully the professors will get back to me soon. :)

The first 4 questions in the assignment are not that difficult but it is very tedious. The biggest difference between CSC 108 and CSC148 assignment is that in CSC 108 I was given detailed descriptions, parameter names and plenty of examples which help me to easily understand what a function should do. But in 148, nothing was given beside from the function names and some short vague descriptions, so I have scan through all of the given classes to figure out how other class to answer some questions. For example, how many parameters do i need, does the function return any value or None, what are the data type of the parameters ...

Question 5 is Hell no more no less! I took me 4 days of hard works until i finally got the solution with some helps from the TA in the CSC help center. The TA there are super nice, one of the TAs sat with me for like 20 minutes, explaining to me in detail what was wrong with my recursive function. Another TA there also taught me how to count no of steps of a recursive function made, which is extremely useful! I rarely came to the CSC help center, i think i came there one last semester for CSC165 weekly exercise but never for CSC108. But from now on, i will come there whenever possible!

The lab this week is about recursion, i and my partner did pretty well in the first two exercise when we are asked to trace through 2 recursive function. But in task3, when i had to code a recursive function, i struggled for an hour and half but still got it wrong at the end. The TA told me the solution, but it made me feel really disappointed about my self. I probably will have to work more on recursion during the reading week in order to prepare for the mid term that is coming soon.

In the scale of 5, i give my self a grade of 3 over 5 for my learning experience, lab performance and effort this week.

Extra # 2 Python goes to sleep!

So this is my second extra blog. Like last time extra blog, i want to show an interesting Python code that i discovered. So here is the code:

import time
def fun():
    start = time.time()
    a = 'ynnuf yrev era uoy'
    for i in range(len(a)-1, -1, -1):
        print(a[i])
        time.sleep(1)
    print('The for loop takes: ' + str(time.time()-start) + 'to run')

So if you run this code, the program will print a message that you may or may not recognize yet, haha! But the point is not the message, but the way it print the message, normally we print the entire message at once but by using the method time.sleep('time in second'), i can delay my print statement each time the loop is executed, generating some sorts of animation. Moreover, i can also calculate the time taken for the program to execute my for loop using the method time.time()!