Recursive Data Structures: Trees

Another week has come and gone.  I can't believe were practically half-way through the semester already.  But nonetheless heres a brief preamble of the material that was covered in lectures.  The topic of discussion this week was trees.  Trees are basically hierarchal data structures, similar to the notion of a family tree.  In the case of a binary tree, every node has exactly one parent, except for the root which has no parent.  Furthermore, each parent node has no more than two children.

As suggested by the title, trees are a recursive data structure, so it shouldn't be surprising that many recursive routines can be implemmented.  For example, questions like 'how many nodes are in this tree' or 'whats the length of the longest path of this tree' can be answered by implementing recursive code.  At first, I found the implementation of these recursive algorithms to be quite confusing.  But after throughly reading over the lecture notes, and the material covered at the following link http://openbookproject.net/thinkcs/python/english3e/trees.html, I have vastly improved my comprehension.

Namespaces in Python

Have you ever wondered where names live in python?  It may seem like a mundane question, but its an important one, and one that doesn't lack intrigue.  Basically, names in python live in namespaces, analogous to how vectors live in vector spaces.  However, this doesn't tell us much, as it only introduces the seemingly abstract concept of a namespace.  To make sense of this notion, lets discuss how python searches through various namespaces when looking for a name.  Specifically, python looks through the following namespaces in order:

(1) Local scope of the innermost function
(2) Scopes of any enclosing functions (if def was in another def)
(3) Global scope (names defined at the top level of the module)
(4) Built-in names in Python such as sum, strip, etc.

This allows python to keep organized, particularly so names outside a function def won't conflict with names inside.

While this is definitely a cool topic (well at least for me) this week seemed to be progressively slow-moving, probably because the buzz with Assignment 1 (which I can happily say I finished!!!).  Anyways, this week should be vastly exciting since we'll be studying 'Trees', literally!

Recursion

This week we spent a considerable amount of time on recursion, and implementing recursive algorithms.  Basically, recursion means that a function can call itself within its definition.  While this provides a way to solve a complicated problem in a simple and elegant way, one must be very cautious when executing a recursive algorithm.   To elaborate, a recursive algorithm must always have a base case (terminating condition), otherwise you will have an infinite recursion, and end up with a runtime error (although other errors could possibly occur).

Prior to this class, my only previous encounter with recursion was with determinants.  To explain, the determinant of an n*n matrix is computed from the determinants of several (n-1)*(n-1) matrices, and the determinants of these (n-1)*(n-1) matrices may then be computed from the determinants of (n-2)*(n-2) matrices, etc.  In this case, the 2*2 matrix serves as the base case, as it can easily be computed.  This procedure is often referred to as Laplacian Expansion.