This week we continued with the concept of recursion and touched briefly on Trees. Of the two concepts, I believe recursion to be the more difficult one-primarily due to the difficulty of finding an incremental step that could be folded down into a base case. The base case however isn't too difficult to discover right off the bat.
Regarding the topic of recursion I have problems imagining an incremental case that will collapse neatly into the base case. Am I just too much of a dullard to grasp this concept quickly? For instance, I can't imagine how I'd handle the permutations function recursively (posted on the website), and I'd imagine that I will experience the same trouble with more complicated examples. Luckily our professor structured the lesson to address such depressing thoughts. He started by framing recursive problems like Factorials and Fibonacci as a tree, and traced the path downwards with arrows; then subsequently retracing upwards to show the effect of a function 'wrapping' itself up to produce a single value.Professor Amir then moved onto introducing a technique which depicts the function calls as elements that are being put in a 'stack' - I found this very useful , but I think I will gravitate towards making tree diagrams more often than this formal method. I think as long as I am consistent with the way I depict function calls I'll be alright.
Regarding Trees, he only touched on a few applications of it but it illustrated the benefits of recursion. He showed several examples which involved calculating the length of trees, the number of branches in a tree, the max branch per node and the number of children - all of which made use of recursion and list comprehension to solve it neatly. I could only imagine the nightmare of coding these problems with loops-I shudder at the thought. Additionally, the ideas of 'parents' and children were introduced and I found that previous lectures on nodes quite useful in understanding this new structure-the trees were simply a collection of nodes that pointed to two 'children'.
Punctuating the discussion of these 2 aforementioned concepts were timed (and presumably marked) exercises that incentivized people to apply the words coming out of professor Amir's mouth. What I discovered is that I need way more practice to be able to answer unfamiliar recursive problems quickly.
Some final thoughts: recursion seems to be the most difficult topic thus far, and the entire course has finally eclipsed the difficulty of 108. Not to disparage CSC 108 but the difficulty of the course came from the final exam which tested our ability to combine all the basic concepts to solve well formed questions; whereas CSC148 starting from at least 1 week ago is leaning towards creativity and much deeper thinking. For now, I think I'll scrounge up problems from some free online courses, notably from MIT.
This particular link: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/unit-1/lecture-6-recursion/ has a good explanation of recursion.
Time to really step up programming efforts it seems, can't wait to see what's coming ahead.
No comments:
Post a Comment