Week 7 - Recursion

Up until now we've been taught recursion at a very basic level with nested lists as our starting block, and have expanded to more complex things such as trees. Through this transition the simple concepts of recursion have stayed stagnant.

Recursion is the process of repeating items in a self-similar way, with respect to functions it is the act of calling a function definition within itself. This in itself sounds like an infinite series of process considering that a definition is made up of itself (which is forbidden in English grammar). The solution to this problem is what's called a base case. A base case is defined as something we know for sure, and is unchanging. For example, if we were calculating the n'th factorial, we always know that if n is 0 then the 0th factorial is 1. Why? Well based on the definition of a factorial (n*(n-1)*...*1). Since 0 is a special case, it is independent of the definition of a factorial, hence we always know the answer to it. Using this base case, we have a result that will exit the infinite calls. This being the case, we just have to make sure that we reduce the larger problem to many smaller problems involving the base case, thus yielding the appropriate recursive result.

It is this ideology of recursion that enhances an individuals thought process to be expanded across multiple areas of thinking, thus altering that thought process to be adaptable to multiple scenarios. Just as we were introduced to recursion through lists, we are now adapting this ideology to trees and linked lists. This is a transition to abstract data structures, which involves some high order thinking yet retains that constant definition of recursion.

Week 6 - Scavenging Tree's

This week we reviewed tree's and various ways to search them involving; pre-order, post-order, in-order. These are traversal techniques which end up exploring every node within the tree, but a particular order. We've learned some new terminology with respect to trees, the main one's being the root, leaves, children and parents. The root is the starting node of a tree, a tree which is defined as a node and all it's children. Leaves are nodes which have no children. Nodes which have children are referred to as parents. All of these terms help us better describe trees, and further in the course will help develop algorithms with respect to trees.

In addition to learning about general trees, we were introduced to the binary tree. This is a specialized tree in which each node only refers to two children (otherwise none) are organized in such a way that the right child is greater than the parent, and consequently, the left child is less than the parent. This organization strategy allows for in-order traversals of this tree to result in exploring the tree from smallest values to largest.

As important as trees are claimed to be, I personally don't find a great use for them right now. We've seen them recursively implemented through lists in Python, but they appear to be more an organizational strategy better suited for Object Oriented Programming architecture.

Week 5 - More Recursion and Assignments!

This week in lecture and tutorial we covered more approaches to recursion. Recursion is a pretty complicated topic to understand, once understood you have to train your mind to think in that "recursive" term. This is something that's plagued me for 2 years (yes I started tackling recursion a mere 2 years ago). I've seen many people fail completely at recursion and those who get it in an instant. I've always leaned towards the failing end, although I would understand the reasoning behind it, I've never been able to code my ideas recursively. This week however I think I've achieved something great in my life because I've realized the secret to recursion and have demonstrated that in tutorial.

When taught recursion in lecture, Prof.Heap made it clear to think of the most simplest case and work up from there, using the values obtained previously to propel your examples further and further until you have a generalized formula. Now although this idea is relatively simplistic to understand, being able to combine this ideology with that of pythonic paradigms is yet another challenge. What I mean by this is list comprehensions. Thinking in terms of list comprehensions seemed like an impossible task when I was first introduced to it, all I could think of was "how did he think of this?". It wasn't until tutorial when I was faced with a similar problem that I was able to think like Prof.Heap and end up coding an example that he would have created himself. This was a moment in which I realized the secret to recursive programming, but much is still yet to be learned.

We have our first assignment due this week, an assignment I figured would be easy like CSC108's last semester. Boy was I Wrong. This assignment is the hardest assignment I've been given, why? Well, this assignment is based around solving a conjecture, something that no one in the world has created a definitive solution to. We are asked to provide a "good" approximation? This is a seemingly impossible task but a task we are forced to take on. I've tried many techniques of thinking of the problem and only have one issue which is how to switch between free stools, this is the trick to the problem but I have no idea how to do it with recursion. Previously I said that I now understood recursion, but I am still not a master at it since I cannot solve this problem.

In summary, this week has opened my mind to many new possibilities of programming, and has also humbled me with the task of attacking a conjecture.