Week 7 - Recursion

Recursion is the application of calling a function inside itself to solve a set of similar problems. As an example:

    def non_list(L):
    '''(list) -> int
  
    Return number of items in list that are not lists
  
    >>>non_list([1,'a',[[3],[]]])
    3
    '''
    count = 0
    for i in L:
        if isinstance(i,list):
            count += non_list(i)
        else:
            count += 1
    return count
   
  

In this example we are iterating over items of a list. In the even the item found is another list, we are able to call the same function, non_list, on the new list. This process repeats for all nested instances of lists, only counting non-list items. The recursive application in this function is how we are able to call non_list from inside itself, to solve the same problem for the inner lists. It is very useful in solving a set of similar problems, however I have not learned any of the applications outside of that yet (if they exist). It seems like recursion is restricted in what it can and cannot do, as to call itself it seemingly must be a similar problem.

That being said we have definitely taken advantage of recursion in 148. It has been used our first assignment, to assess and analyze trees, as well as in our lab of linkedlists. It was extremely advantageous and reduced the time needed to solve problems like those, so I can definitely see why it was learned. Initially, and from reading slogs I can see others often agree, recursion was a bit difficult to wrap our heads around; we had never traced anything like a recursive function. But through course readings, lecture examples, and hands-on work in the labs and assignment, I feel that I am now much more adjusted to the concept, and can use it to my advantage in the future.

Week 6

This weeks' series of lectures was based are trees, which can be used as a visual representation of data.
.

The parts of this tree, called nodes, can be described with more specific terms;

The node that serves as the spawning point for other nodes is called the root. ie: 8
A leaf is describe as a node with no children; it is the end of the path. ie: 1,4,7
The 'middle' nodes are internal nodes, such as 3,6, and 10.

Trees can be analyzed through another subject we have learned; recursion. As an example, lets say we want to count the number of nodes in this tree. We can create a count function such that

def count(t: Tree) -> int:

    """How many nodes in this Tree?

    >>> tn2 = Tree(2, [Tree(4), Tree(4.5), Tree(5), Tree(5.75)])

    >>> tn3 = Tree(3, [Tree(6), Tree(7)])

    >>> tn1 = Tree(1, [tn2, tn3])

    >>> count(tn1)

    9

    return 1+ sum([count(c) for c in t.children])

 

In this example we use recursion to access and count the nested lists (aka  the children) of the tree. We are able to count all the nodes using this method. The reason recursion is so useful is because a tree often presents multiple paths leading to multiple ends. Through recursion however we can account for all these paths, and come to conclusions based on the whole picture.    

Week 5

The classes this week once again focused on recursion, but also on the new topic of namespaces and scope. We learned that there is a hierarchy for namespaces that python searches through to use:

• innermost scope (function body, usually) local
• enclosing scopes nonlocal
• global (current module or __main__)

When python is searching for how to perform an action, it searches through this list from top to bottom; if it finds a local solution, it will not use a built-in for example. This can be useful for if you only want to reference something inside a function or clas, while also having it perform a different action outside (or at least, that's what I think it's used for). Going through some other SLOGS, I found many other students have had trouble of tracing the code example of namespace presented to us, and I agree that it went a bit over my head initially. However, now that I have had some more time to analyze it, it seems a bit clearer to me at least.

The lab this week was, well, average as usual. We programmed simple examples of recursion, and I can see now how applicable it can be in large situations with similar problems. Speaking of which..the A1 deadline is approaching, and for (my partner and I) at least I think it is going well. The recursive four stools function looks a bit daunting, but given the move_cheeses example that Prof Heap gave us it seems a bit more manageable (I hope!).

Week 4

Class

The focus of this week was on recursion. I had a general sense of what recursion was already, but previous to this course I wouldn't have had an idea of how to program it. In a programming sense, recursion is the use of a function within itself to solve a larger problem. That probably isnt the most transparent definition, so I will use an example.
(borrowed from http://stackoverflow.com/questions/479343/how-can-i-build-a-recursive-function-in-python)

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

In this example, to find the factorial of a number involves calling factorial on itself. If we had in input of factorial(3), it would return 3*(factorial(2)). Of course, factorial of two would be 2*(factorial(1), and factorial(1) =1. All this happens within the same function to produce the result of 6. It is a useful concept for solving a problem with many similar and linked parts.

Assignment 1

My partner and I began assignment 1 this week, and I have to say I am enjoying it. As always, when presented with large amounts of code at the beginning it may seem like a towering challenge, but once you dissect it into smaller problems it quickly became easier. At this point we have done steps 1-3, and it was definitely a nice reward that after this  point we were able to play a working version of the puzzle. The contrast in this assignment compared to those in 108 is present. While there it seemed we were spoon-fed what to do, and not given much slack in what we could and could not do, I found in 148 there is much more freedom in how we approach a problem.


That's about it for this week!