Assignment Topic Two: Warming up to Recursion.

        Recursion is a technique in which a large problem is broken down into smaller ones. To define something recursively means to define that something by a relation to itself. For example a value in the Fibonacci  sequence is defined as the sum of the two last values in the sequence. This seems ridiculous because an origin has not yet been given. For any recursive algorithm to work it must have a base case(s) and at each step of the algorithm get nearer to that base case(s), otherwise the program will spiral out of control or simply crash.

        In the case of the Fibonacci sequence the base case or origin value is the predetermined value of 1 for the first and second positions in the sequence. In code a function utilizes itself to solve easier and easier problems until it can return a concrete value.

def fib(p: int): -> int:
""" Return the Fibonacci value at a given position, positions start from index 0 """

    if p == 0 or p == 1:
        return 1
    else:
        return fib(x - 1)  +  fib(x - 2)    #This is the recurrence relation that defines the sequence.


This is a decent structure of basic recursive functions. At a more complex scale there may be iterations and many base cases that have to be considered.

        Often recursion is a viable solution when either the pattern or objects you are working with are intrinsically recursive. These objects can come in the form of  recursive data structures such as trees. A tree is an object with a root and branches. The branches are defined to be other trees. In this case you're forced to think recursively from the get-go.

        Recursive definitions need not only be algebraically understood. Some recursive algorithms can be geometrically based. The traversal algorithms of binary trees ( trees with only 2 branches) demonstrate this process. The in-order traversal algorithm has you start at the root, print the value, and then move to the left branch before moving to the right branch. Except once you move to the left you're now at what may be a new tree and furthermore means that your position is the root of this sub-tree. This restarts the algorithm (as the function would recursively be recalled upon in the body at this point) and continues to do so until a branch is no longer a tree itself.

        Often unlike their algebraic counterparts, geometric recursion is easier to trace than it is to represent in a clean recurrent relation. This largely takes practice and for beginners some faith in the algorithm for the behaviour with respect to base cases to translate to greater depths.
     
        Recursion depth is simply how many times the larger problem has been reduced to a smaller one. From the fib function above it can be seen that it continues digging until it reaches a concrete value of 1 and then as it climbs back out it evaluates the problem one level above using that concrete value to generate a new concrete value to be used in the next highest level. So there needs to be a clear path back up to the surface.

        Recursion is a very powerful tool when used appropriately. It can however be overly complicated to introduce recursion to problems that don't necessarily require it. As with any computer science problem you need to begin with a simple example you know how to compute and then dissect the steps you take (often implicitly) to find the solution. Those details define the type of function or program that is written.

More Recursion and Trees

        The week before reading week has got to be one of the toughest weeks of the academic year (except for maybe the final week). So there's been a delay on this post as a result. 

        I'll start positive. The lab over a week ago did supply good practice with recursive functions. I still feel, while comprehensions are nice, that code should be indented (python) and done in blocks for clarity. This is particularly with regards to " if statements" that become an absolute mess otherwise. Speaking of this, this past week's lab oddly had us interpret code written using comprehensions and functional programming techniques and re-implement the functions using the style we've always known. This just means there's some confusion as to how I'm expected to code on the tests/Assignments. Dustin did mention he'd send an email about this and other material we're responsible for on the test.

        We also looked at trees this week. They seem simple but the pre-, in-, post- , order traversal algorithms can give your brain a workout with some very large cases. This is precisely what I intend to do in preparation for the test. In-order traversal is probably the weirdest as it moves left to root, then to right, and  not merely root to children, or children to root as in pre/post-order traversals respectively.

        A1 marking should start from tonight onward. I do hope on the next assignment that they make the instructions far more clear and  more importantly ensure the starter code is not fraught with errors. Now I must return to studying. 

Comments: Recursion and Testing.

        This last week was largely comprised of exposing us to lots and lots of recursion examples. That being said we don't get much of a chance to interact with them.

        Yes the code is available to us on the course webpage.

        What I'm getting at is seeing recursion being used to solve problems is different than having recursion in your tool box, attempting a problem, and ultimately realizing recursion is a viable path to a solution.I think it would be more effective if we'd be given some very easy practice problems to warm up with and get a sense of the technique of recursion. Instead of merely seeing solutions of problems using recursion and then be expected to implement a rather difficult one on a our assignment this week.

        To get a sense of the technique is particularly what I've sought out to do recently and after scouring the internet you find some useful tips. You want to break the function down into two parts (for a simple problem) in which either the argument falls into the category of the base case(s) or that it must be reduced to the base case by simply following the pattern. In a later week for the class I will have to publish a post dedicated specifically to recursion so I'll end things here.

        I'd rather be coding (this is actually with respect to the lectures) but if I'm going to sit in a lecture hall for two hours watching a power point presentation I'd rather the lecture systematically describing how I should go about implementing these techniques (especially if they're new) than just show us lots of examples with no preface.

        OK, I've reached my complaint-quota for the week.

        Aside from recursion, unittest became much more interesting. In lab we utilized the fact that since tests are considered classes they can be the subject of inheritance. The only caveat is that the ability to reuse a particular test usually means that it is very general in nature, although, anything that reduces duplicate code is almost always warranted. Also the setUp and tearDown methods are great. No really -  why they weren't covered in the prerequisite course where we often did create unittest files is mind boggling.