Week 7

Wowwwww! It's already the 7th week of this course, I am so surprised that the time in this semester went even faster than the last semester. Maybe I just have a lot to learn in csc148 and don't really have time to chill. I just done my first mid-term today and it was tough. I think I'm going to get probably a 50 out of 100. That means I probably have to work harder in the future. 

So this week's topic is Recursion!!!!!!!! Some thing that is very useful but also can be extremely tricky if you don't get your logic right. Let me give a brief introduction to recursion.

First, start with the question, when do we need to use recursion? When we are solving a problem by repetitively using the same trick over and over again, that's the time we should use recursion. Recursion works like a while-loop, basically we put the header of the function in the return statement so when it gets to the return statement, it calls the function again. This is a very important logic in programming since it is used in many different programs. Here are some examples of recursions that are shown in class:

def rec_max(L):

     """

     Return the maximum number in L, possibly a nested list

     >>> rec_max([12, 25, 0, 3])

     25

     >>> rec_max([11, [18, 36], 0)

     36

     """

     return max([rec_max(x) if isinstance(x, list) else x for x in L])

As shown above, the function will go through everything in the list and when it finds a nested-list, it calls rec_max again and put the nested-list as a parameter, else, it'll append the number to the new list. Finally, return the maximum number in the new list. This is a very simple recursion and I believe more will be introduced in the coming weeks.

It is very important to find the stopping point of the recursion when we are writing it or it will go to infinite recursion and the computer won't have enough memory to handle it. Simple stopping points come from using for-loop over an iterable object, just like the example showed above. We can also create a condition so that when the recursion hits that condition, it'll stop. Just like a while-loop. 

Recursion method is extremely useful since a lot of programs are repetitive and will be using recursion in it. For example,  for the Binary tree that has been introduced to us,  a lot of sub-functions in it are using recursion. In addition, Assignment 1 that we have handed in also require us to have a deep understanding in recursion in order to solve it. There is no doubt that recursion will be used very often when we are working as programmer in the future. 

Honestly when the professor first introduced recursion, I was lost in the middle of the Pacific Ocean, have no idea what he's talking about and how the codes work. However, I found that when I actually grabbed a paper and pen and started the trace the program, it was ten times easier for me to understand the codes rather just read the codes over and over. Although it might take quite a lot of time to trace a recursive function, the process really gave me a lot of insight on how the recursive function works and when can I apply the recursive function.

Thank you for reading this blog. I hope I'll share with you soon.

Week 6

What's up everyone I'm back. I was struggling for awhile whether I should write this blog or not. As I mentioned last week, my first CSC148 assignment is due tomorrow. Although my partner and I already had some clue on how to write the Tour.py, we have not written it out yet so we won't know if the codes will work or not. However, I felt that really need a break from the intense programming so I'm writing this blog now. (FYI I'm programming with my partner at Bahen now and we are ready to pull a all nighter) Please forgive me if this blog is not as good as the previous blog that I've written.

oh ya. I've made all my lectures on time this week!!!!!!!! and I'm glad that I made them because a new and interesting topic was introduced this week, which was Trees. Yes, I'm not talking about Biology or Geography class. We were learning Trees at computer science class. You can think of Trees as a special method for storing data. At this week's lectures, Binary Tree was introduced. 

Let me try to explain what is a Binary Tree:

In each tree there're roots. Each root can have a left child, a right child, or none. And each child can be a root itself......... etc. As more and more data was being stored, there'll be more and more roots and children in the tree.

I think the interesting part is that we can traverse the trees in different way. Up to know, three ways of traversing were being taught. They are: Post-order traversal, In-order traversal and Pre-order traversal.

Take it this way:

Post-order traversal = visit left then right, then root

In-order traversal = visit left, root, and right

Pre-order traversal = visit root, then left, then right

For example:

post-order traversal of this will be: 2, 5, 11, 6, 7, 4, 9, 5, 2

in-order traversal of this will be: 2, 7, 5, 6, 11, 2, 5, 4, 9

pre-order traversal of this will be: 2, 7, 2, 6, 5, 11, 5, 9, 4

All of this can be done by recursion, amazing right?

This is very fun too do, and it's a good practice on recursion too. I think for the coming weeks I'll be practicing more on Trees so that I can learn how to write different functions in it. So that's it for now, I need to get back to Assignment 1. Hope we can finish it tonight!

Check for my update next week, see ya!

Week 5

Hiiiii everyone, welcome back to my blog!!!!! One week has gone by super quick and I was very busy with all kind of school work. And yes, first assignment in CSC148 is due next week.................. my partner and I has already finished the first few parts but when it has come to the 5th part, which we're supposed to implement the codes for Tour.py, we're stuck and currently pretty much have no idea what's going on. I'll discuss that later.

SOOOO remember that I mentioned that I skipped a lecture last week? This week I have tried my best to attend the lectures that turned out I was only late for one lecture. Big improvement isn't it? I'll try to attend all my lectures on time next week and I'll report to you guys how i'll do.

Although I've been to all the lectures this week, I found that I didn't really learn much from lecture. I'm not saying that the prof did not teach well. Instead, he taught a lot of things on recursion and also explained to us what is the Tower of Hanoi. I didn't learn much because I wasn't able to understand much during the lecture. I have to admit that I'm quite slow at understanding recursion. For example:

def  move_cheeses(n: int, source: int, intermediate: int,destination: int) -> None:
           """Print moves to get n cheeses from source to destination, possibly using intermediate"""
           if n > 1: # fill this in!
                 move_cheeses(n - 1, source, destination, intermediate)
                 move_cheeses(1, source, intermediate, destination)
                 move_cheeses(n - 1, intermediate, source, destination)
           else: # just 1 cheese --- fill this in now!
                 return ??????

we were asked to complete the return statement but it took me sooooo long to figure out how the recursion will run and I wasn't able to complete it during class. I did figure it out after class when I sat down in the library and started tracing it so I guess it's not that bad.

I found that this week's lab was super helpful for me and I learned A LOT from it. We were asked to trace a couple of codes that were using recursion. After my lab partner and I finished tracing them, I felt like I suddenly have a way deeper understanding in recursion, especially knowing how to find the base case. As my TA has said, "there's no better way to understand a program than tracing it on paper". This is totally true. I'll never be able to understand recursion without tracing different codes on paper and looking through them step by step.

Back to assignment 1, at part 5, we were supposed to use recursion to solve the Tower of Hanoi with the least possible moves. Our codes should be able to apply no matter how many stools or cheese there are. For example, our program should be able to solve 4 stools and 5 cheeses in 13 moves but it failed. Currently we have no idea what's going with our program. Maybe there's something wrong with our recursion, we really don't know. I'll bring more updates to you guys next week.

So that's it for now. see you guys soon!