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.