Topic to be graded : recursion

This week, we learned recursion. Basically, recursion is a technique that using the function itself as a helping function and call itself. With this method, we can dive into many sub problem and solve each of them by the similar technique and finally solve the bigger problem.

Recursion is like doing a puzzle. Whenever you get into a cross road, you choose one first, and when you touch the bottom, the program start to backtracking and try the other possibility. So we can traverse all the possibility with recursion because we tried all the path from top to bottom. To be more precise, let's say we want to find the sum of a list, for example [1,[1,2],3,4]. Using the normal method sum function will give us a error because the element [1,2] is also a list in the whole list. To solve this problem, we can use recursion.

def Sum( L):

        if isinstance(L,list) :
                 return sum([Sum(x) for x in L])
        else:
                 return L

This function is easy to understand, whenever we meet a list, we call Sum again to put all the sub element in to a list, and finally return all the sum and get the answer. However, I met a problem that require us to find the longest length of a list. For example, [1,[1,2,3]] will return 3, because the sub list [1,2,3] has length 3 which is the longest. If we use the same method as before

def  length(L):

        if isinstance(L, list):
               return max([length(x) for x in L])
       else :
               return 0

we will have two problems. Firstly, we did not add the length of the most outside list in the comparing list. Secondly, what we put into the comparing list is all the sub element instead of the length of the list. So we change it to

def length (L):
    if isinstance(L, list):
         l = []
         for x in L:
             if isinstance (x,list):
                 l.append(len(x))
         l.append(len(L))
         maxLength = max(l)
         print(l)
         for x in L:
            maxLength = max (maxLength,length(x))
         return maxLength
    else:
      return 0

will solve the problem because it get maxLength in a level and compare it with sub list leave *maxLength.

some thinking about the learning of python as a c/c++ programmer

Wow, to be honest, I did not take CSC108, so I have no python experience before CSC148. But I have used c/c++ for two years, basically, use it for computer programming contest. I used to do a lot of programming contest problems. Usually, most of my time is spent on debugging.

When I use c/c++, it is much easier to read the program and see the logic inside every loop and condition. But when I go into python, things start to mess up. I am not comfortable about not declaring variables before using it. Sometimes, when I am reading a python program, I get lost and confusing about the meaning of the variables. Compare to c/c++, python is a much easier language because it is more similar to human language and many complicated concepts like points, arrays are replaced with higher level functions. However, it is hard to balance convenience and making thing clear.

For example, since python does not require define variable before its usage, to make program readable, it requires python programmer to write doctest to clarify input variable type and output variable type. And when a python code is translated into machine language, it usually cost more time and memory to " understand " the code since everything in python is kind of auto type.

For these reasons, it tells me that it is very important to write a clear doctest  and follow professional python coding style to make a good python program. Also, keep writing a blog to record your learning experience and debugging process is a helpful way to make out programming skill better.

Test for the blogger