Recall Week 4 to Week 6

On week 4 we talked about the recursion, thought we've been using recursion functions in programming language courses, and I hated it since it is hard to follow what is going on compare to a loop. This chapter will helped me understood the recursion better for sure. The Fibonacci sequence is used for demonstrating the unwind steps. I actually found it was quite hard to convert a expression that is originally defined in the recursive way, to a one line mathematics equation. I did tried some related problems, and found they are all very useful, but I guess the core reason is that I do not feel safe with recursions, by this I mean it is harder for me to monitor each steps, unlike a for or while loop, though as a matter of fact other people may find it is neat to use a recursive call rather than a loop. After that we focused on the recursive binary search function. We followed through the steps and I find it's really useful to actually sit down and see what each variables and the return value can vary after the first time, the second time ... until it hits the stop point. The last part is the Time Complexity for a function. We actually did the similar topics in CSC165 and I still remember we used the big O to give a approximate timing for the worse situation that a program can happen. It become more precise here. Actually we do know the logN is the time complexity for binary search, but it is still cool to see we actually proved it.

In week five we went through closed form recursive functions, and in week six we were dealing with an instance of sort algorithm called merge sort. The merge sort is kind of nice; as it keeps dividing the huge thing into small pieces, until it reaches the size of 1, then combine them together. And this leads to the divide and conquer theory. Honestly speaking I am really not that familiar with these two chapters, but I will definitely take a close look when I begin to do the review work. Besides, we also did some unwinding stuff and proof. Unwinding seems pretty easy, but I found it looks easy, but when you actually sit down and do some problems you will find it takes some tricks to unwind, at least for me. It is not that straightforward as proof. I should work on more similar problems to make myself comfortable with this.