Week 11: Revisiting a previous post

Note: Links to blogs that I have commented on or read have been included in this post. 

I have decided to revisit last week's (week 10's) post, as it describes the continuing struggle I have faced with grasping and mastering recursion. I wish I could say my approach to learning recursion has been anything other than brute forcing my way through a problem until I obtain a correct answer, or learning through mimicry, but that would be a lie. 

Recursion is the one concept in CSC148 that I have struggled with, and it is a fundamental concept that all programmers should have a strong understanding of. 

In week 7 of this course, I defined recursion in my own words:

"""
Recursive functions are functions that call themselves. If a task can be divided into identical, smaller sub-tasks, this is a good indication that you can perform this task by recursion.

They have a conditional structure that specifies a base case (or cases): a condition (or conditions) that will stop the function from making calls to itself.  The also have a general case, which specifies the method in which recursive sub-calls will be combined. Essentially, the general case is the part where the function calls itself. It is important that you designate a base case, or the function call will reach a maximum recursion depth, and result in a stack overflow.

What is this legendary stack you speak of? Recursion is actually a method of using stacks to achieve a task. However, call stacks are stored in a computer's memory, and these stacks cannot become infinitely large, as computers do not have an indefinite amount of memory space. Thus, when a recursive function has a bug, and never reaches a base case, the computer will eventually runs out of memory and crash the program. This is called a "stack overflow".
"""

I think recursion is definitely a concept that does not come easily to me. It will most probably be a concept that I gradually come to terms with as I grow as a programmer. It is certainly a new, and unused way of approaching a problem that I have never personally encountered prior to this semester.

I worry for myself, as I am concerned that I will not do well without having a fully understanding of recursion going into the exam and into 2nd year programming courses.Regardless, all I can do is try harder.

I think the one thing that keeps me afloat is realizing that my struggles are not unique to just me. 

For example, here are a list of blogs that I have either read or commented on:

https://humaircsc148slog.wordpress.com/2015/03/15/week-9-back-to-bsts-insertions-and-deletions/comment-page-1/#comment-2  Humair takes time this week to describe Binary Search Trees and various methods associated with these classes. Humair always takes the time to write informative posts, and it's always informative to see how my peers approach different problems. Humair's blog has been a pleasure to read this semester

https://csc148winter2015.wordpress.com describes their journey with recursion, and how they developed over the period of a semester. Notably, the writer finds that they learned how to approach recursion in their own unique way. 

http://christiangarciacsc148.blogspot.ca/2015/03/week-10-impressions-of-week-9.html?showComment=1427568192945 always takes the time to create clear and concise diagrams to help his peers understand topics. His posts are always informative. In one of his posts, he mentions a quote from a fellow student that he found guided him through his learning: 

“I think the key concept is: don’t start [from] details but start from structure.”

He proceeds to state that: "This is definitely a good advice to take home. Structure is really important when programming. A clear structure can help not only the person coding, but people looking at that code. Also, having a plan before starting anything helps to clarify ideas and to have an easier time coming up with a solution."

I think, ultimately, that recursion is as complicated as you make it. I have to learn how to simplify problems. To not overthink things, and to take things slowly. Rather than coding desperately, and trying a billion solutions until I find the one that works, I should rather just sit down and pause. Think about the core problem I'm trying to solve, and let things fall into place. 

I think one's approach to solving a recursive problem could actually be indicative of one's approach to solving every day problems. 

I'm normally a highly stressed individual who sweats all of the details. I angst over the trivial technicalities, and fail to see the larger picture at times. I have long since come to recognize this problem, and I continually work to change this aspect of myself. Hopefully, as time passes, I will be able to apply a calmer, more methodical approach to solving problems both in my programming life and in my everyday life. 

Week 10: Assignment 3

Again, the strike continues, and it's beginning to take its toll. I haven't really been following up on the lab material, as I should have, because of the chaos that has been going on. Debates being turned into term papers, assignments being pushed forward or pushed back. It's been a crazy time. In particular, the wording of the last couple of labs has been a little confusing and off-putting for me, and I'm not very sure how I should approach them.

Regardless, I've been working on Assignment 3, and it has been successful for the most part. Again, in this assignment we are working with trees. However, the tree is composed of GameStateNodes. I found that this lab required an extensive use of helper functions that simplified the assignment for me.  The difficult part was identifying the helper functions that were needed.

I had problems with two of the functions in the assignment, but these problems were fairly quickly overcome. Strangely enough, I found that assignment 2 was leaps and bounds more difficult than assignment 3. This may in part be because I chose to complete Option B rather than Option A, which seemed to be a longer undertaking.

Anyways, branching_stats was one such function that I had difficulties with, as my preconceived notions of dictionaries in Python were lacking. I kept attempting to use the .add() dictionary method, to no avail. A little tinkering around with dictionaries put me back on track.

Another function I had difficulties with was a helper function I used to collect all of the paths in the tree. I had difficulties conceptually seeing the path I had to undertake so as to obtain the path in each tree. Although I could see how I would go about doing this visually, I had difficulties translating it into code. After deriving the solution for the answer, I was saddened by how simple the answer really was, and how long it took me to find the solution .

I think recursion is definitely a concept that does not come easily to me. It will most probably be a concept that I gradually come to terms with as I grow as a programmer. I worry for myself, as I am concerned that I will not do well without having a fully understanding of recursion going into the exam and into 2nd year programming courses.

Regardless, all I can do is try harder.

Week 9: Optimizing Recursion

Thus far in CS148, we have learned that while recursive functions are often more elegant than functions that use loops, they are often not as efficient. However, there are ways of optimizing recursive functions.

For example, in a recursive function on a tree, you can choose to ignore branches of the tree that will not impact the output of your function. This reduces the number of recursive calls you make on your tree, and optimize the efficiency of the function.

        

    # The optimization here is that you can ignore branches. So you add conditions to IGNORE them.

    # When do you ignore the left branch? When node.data < start.

    # When node.data < start then you ignore the left branch.

    # See below:

    

    def list_between(node, start, end):

    ''' (BTNode, object, object) -> list

    

    Return a Python list of all values in the binary search tree

    rooted at node that are between start and end (inclusive).

    

    >>> b = BTNode(8)

    >>> b = insert(b, 4)

    >>> b = insert(b, 2)

    >>> b = insert(b, 6)

    >>> b = insert(b, 12)

    >>> b = insert(b, 14)

    >>> b = insert(b, 10)

    >>> list_between(None, 0, 15)

    []

    >>> list_between(b, 2, 3)

    [2]

    >>> L = list_between(b, 3, 11)

    >>> L.sort()

    >>> L

    [4, 6, 8, 10]

    '''

    if node is None:
        return []
    else:
        left_list = (list_between(node.left, start, end) 
                     if node.data > start 
                     else [])
        right_list = (list_between(node.right, start, end) 
                      if node.data < end 
                      else [])
        node_list = ([node.data] 
                     if (start <= node.data <= end) 
                     else [])
        return left_list + node_list + right_list

Week 8: Linked Lists

In week 8 of CSC148, we learned about Linked Lists (LLs).

Summary of Linked Lists:

- Linked lists are data structures
- Linked lists are similar to trees in that they utilize nodes.
- These nodes are represented as a sequence.
- Linked lists are similar to arrays (lists), as they both store data.
- However, there is a unique difference between lists and LLs.

- In a vector, if we wish to insert data into our array, we have to move all of the subsequent entries by one or more indices. Although this is not too much of a problem when we have a list of length 1 or 2, this becomes a huge undertaking when we have a list of length 2,000,000. The amount of work grows in direct proportion to the number of items in the list.
- Insertion and deletion operations in an array grows linearly with the number of entries.

- We can use another data structure to perform an insertion or deletion operation that is independent of the number of items in the array : the LL
- In a LL structure, each of our nodes is linked to the node following it.
- We access elements in a vector through indices. Each element is contiguous to one another
- In a LL, the way we get to another node is through links that use pointers to point to the memory address with the next node in the LL. We also have a terminating value for our last node in the list to indicate that it is the end of the list.

- To insert a new element in the list, all we must do is grab one of the pointers in the list (let's call this point A) and point it to this new value (C). Initially, node (A) was pointing to node (B). So, we can point this new node (C) to point (B). In a LL, we can have a million values, but all we have to do to insert one node is redirect those three values. This is in comparison to having an array with a million values. Nifty!
- However, vectors(arrays/lists) excels in different ways. Although LL are superior for insert/deletion. It does excel at being able to access any particular element in a constant amount of time through the power of indices.
- In the case of LLs, you must follow the pointers throughout the LL to "find" the node that we're interested in. In LLs, we only have a mechanism to go forward, and we must start at the front of the LL and traverse the entire LL to "find" our node.
- WLists can go backwards, but we have not covered this topic.