Week 7 - Recursion....wait what, again?

This week's assigned slog topic is recursion.  I'm half tempted to just refer you to different sections of week 4, but I'll re-iterate and expand on what I've already written anyway.

To start, let's review; recursion is a tool used in computer science to perform a specific task recursively, ie a function that calls on itself during it's execution.  (I'm quite sure that most recursive functions take iterable objects as an input, like lists and other list-like ADTs).

I previously likened recursion to the chain rule differentiation through a pretty complicated example, but now I realize there's a simpler example.  Consider the concept of factorials in math (!).  When you take a factorial of a number, you multiply all the integers from 0 up to that number.  This can be implemented in the following python function:

The above code is easy enough to read/understand, however the factorial function can also be implemented using recursion, like so:

Lets trace it - if you input the value n = 3, then the function will check if the value is 0, since 3 != 0, it then goes to the last line, 3 * factorial(3-1).  The factorial function here calls on itself, going through the process to see if 3-1 = 0 (it doesn't), so it proceeds to the last line again to give 3 * 2 * factorial (2-1), which then repeats again, giving 3 * 2 * 1 * factorial(1-1).  This time, however when 1-1 is inputted as n into the function, 1-1 does indeed = 0, hence returning 1.  Hence the final output for factorial(3) turns out to be 3 * 2 * 1 * 1 = 6.

List comprehensions are used a lot when we deal with recursive functions since lists can be nested.  Consider the following problem - we want to find the the max of the items in a list (that can be nested)  How would we go about this?

List comprehensions make the code for this problem relatively short:

Even though the concept of recursion is simple enough to understand its implementation can get quite complicated depending on the data structure you're working with - more complicated ADTs make it even worse.  However, I find the trick to tracing recursion is to not think too much...if that makes any sense.

Week 6 - I See Trees...of Green....Red Roses Too....

This week we covered Trees in lecture; more specifically, binary trees, and honestly I was completely lost during lecture.  Hopefully by reading up on Trees more as I write this slog, the class will become more clear to me.

Lets start with basic definitions.  This'll be easier with a diagram, so consider the following:

The above tree is a binary tree since every node (represented by the circles) has two child nodes.  The top node (here, labelled 'A'), is called the root, and the nodes that do not have any children are leaves. However, since we're in code we don't really have nodes that have nothing branching from them - Nodes can either store either values/objects or Nonetypes.  If a node has two Nonetype children then it is a leaf.

Trees are recursive data structures; they're either:

• Empty (represented by None) or
• A node that contains an object and/or two other tree references

So now we have the 'graphical' representation of trees, but what do they look like in actual code?  Luckily for me this was shown in-class, so consider the code taken from Monday's lecture:

As you can see from the code, Trees are a lot like the nested lists we examined in Week 4 (as well as Lab #4).  Note that if there are no children, the line self.children = [] creates indexes with the Nonetype where in place of a leaf's child nodes.

Week 5 - Scopes and Namespaces

First thing's first.  Changes to assignments should not be emailed by the profs after one has finished the assignment.  Just...no.  Needless to say that all the time spent in lecture on discussion TOAH model and assignment 1 in general would've been better spent last week (personally/for my group), but it was a good confirmation that our group hadn't gone in the completely wrong direction, but I digress; at least there will be less to write about in this week's slog.

What new material we did cover in lecture revolved around how Python handles scopes and namespaces.

But before we begin, what is a name?  Remember from CSC108 that Python names refer to a memory address which contains an object, being a value, function, class, etc.  A namespace is ...well a space that holds several names.

Consider a Python module/file (insert_name_here.py).  Each module has its own global namespace, so that all the names used in the module are in the same space.  Because of this, no two objects can have the same name, unless they are nested (but more on that later).  Even though each individual module has its own global namespace where no two objects can have the same name, you can import different modules into your program.  When you do this, there can be a name shared by both modules that refer to different objects.  For example if I have the file stack.py with the class method is_empty(), and queue.py with the class method is_empty(), they can both be called separately by importing both modules (import stack and import queue) and then typing stack.is_empty() and queue.is_empty().  However note that if the program has an is_empty() function, access to the functions of the same name from stack and queue will be lost.

Scopes are regions of a program from where a namespace can be accessed without a prefix (like the above where the prefix stack. referred to the module name).  At any time, there are several different scopes being used in a program - the scope of the current function, module, and the Python built-ins.  If the functions/modules are un-nested, they cannot access names from other functions/modules in the program.  For a simple example consider the following:

Even though the functions scream and shush have the same variable names s and new_s, the two functions still work when they are called in the shell without interfering with each other.

However, what if the functions were nested?  Consider the following example from class:

First, Python acknowledges that the functions do_local, do_nonlocal, and do_global exist before executing spam = 'test spam'.  The function do_local creates a spam that is local, meaning it only exists in the scope of the function do_local and not in any other function, even scope_test.  When the do_local is called later within scope_test, the value for spam is automatically trashed after the function finishes executing.  In do_nonlocal, the operation nonlocal makes it so that the spam that do_nonlocal uses is the spam from the encompassing function scope_test, which states that spam = 'test spam'.  However the next line of the function dictates that spam = 'nonlocal spam' which changes the spam in the encompassing scope as well.  When do_global is called, since at this point, there is no name spam in the global namespace, it creates a global variable spam, and then assigns its value as the string 'global spam'.  However, because do_global() is being called within scope test, and not the global scope, it prints the value of spam that is within the local scope of scope_test, which at this point, from the previous assignment of do_nonlocal is the string 'nonlocal spam'.  When the function finally exits scope_test, and prints spam, it first searches the local namespace, and fines no name spam in that namespace so it then checks the global namespace, to find that in the global namespace, spam = 'global spam', and hence prints that.

So in summary, python always looks for names in different scopes in the following order:

1. The innermost scope - local variables
2. Encompassing scopes - nonlocal variables
3. The global scope - global variables
4. Built-ins 

Namespaces are, in my opinion, can get quite confusing, but since we haven't encountered any really complicated code that involves switching between many layer of nonlocal scopes, it hasn't been too difficult to use.

...But I'm sure we'll be dealing with really confusing scenarios on the term test.  Which is in less than two weeks.