Week 7 - RECURSION!

Hi everyone!

This week is the big post about recursion. I know I've posted about recursion before but this post is going to sum[everything about recursion] (hehehe get it?)

Recursion, in computer science, is a method where the solution of a problem consists of the solution of smaller problems which are subsets of the whole problem. For our convenience, it's basically calling a function on an object repeatedly until a base case is reached. 

To do code recursion in Python, we call the function itself in its own function body, but it's what we want it to do that differs between different recursive functions. Quoting myself from week 5 "I feel like the one most essential thing in recursion is to always call the function itself in its own function body, and it will call and call again until it reaches a base case, in which case the result will be evaluated."  Follow this rule and you pretty much have recursion in the BAG. 

Then we will be able to determine the solution of the main problem from the solutions of the base cases. Most of the time, we would use recursion on things that are nested within itself, especially data structures, and Trees are a prime example of this. (See week 6 post for full Tree explanation).

This week, we encountered recursion in the labs through LinkedLists. A LinkedList is pretty much a tree with a maximum of one child (think the Chinese 1 child rule). The end of the list is reached when a node has no children. The problem of the labs this week was a stack taking the form of LinkedLists. Similar to week 2, I had trouble with this because I couldn't figure out how to keep the pointer on the back of the list with the enqueue function.

CONFESSIONS OF A COMPSCI GIRL: I couldn't figure out how to do enqueue this week and my partner and I tried so many different things and it wouldn't work. WE EVEN TRIED INDEXING THE LINKED LIST WHY DID WE DO THAT? Lesson 2 in Trees: don't index them. OMG don't do it please please please or else you'll face the wrath of the Computer Science gods (aka the Python shell) and will unleash the utmost horrifying consequence on you (EXCEPTION! OH GOD NOT THE EXCEPTION)

So in the end the kind TA (Abdi you're the best) explained everything to us and VOILA (I feel like I cheated though because I couldn't figure it out myself T___T) but basically we set a variable to the last empty "node" of the LinkedList, and just prepend to that.  REMEMBER THIS, I feel like this will help with recursion and data structures for like the rest of my life.

TATA FOR NOW FRIENDS. See you all next week :) !

week 6 (PHOTOSYNTHESIS)

Hello once again, dear readers! This week we have a bit of a long post. Hard to summarize so much information about plants in such a short post right? ;)

So this week we delved even deeper into recursion. We learned about trees, leaves, edges and roots. Before you go and think it's about plants (for those of you who didn't attend lecture and think we suddenly turned into a biology course), it's actually about data structures.

If you think about it, we've actually had an encounter with trees last week in the labs, with the SearchList. The 0th element was the root, the 1st and 2nd elements were its leaves. Each of the elements could have had either more leaves (up to 2) or None (and None was a base case). Maybe this was Danny's way of preparing us just in case some of us actually thought CSC148 was turning into a biology course.

But all in all, summing trees up. Trees are made of nodes, and there's always a node that's referred to as a root (the one node with no parents). It may or may not have children (and the children are referred to as leaves), and parents are connected to children via edges. In the diagram below, we can see that 1 is the root, and 2, 3, 4 are its children. All values are nodes, and each of the arrows connecting the nodes are the edges. All trees have subtrees.

(Source: http://new.math.uiuc.edu/math198/MA198-2009/lee522/pix/frame_tree_diagram.JPG)

Through learning about trees, we also got some practice with list comprehensions. I thought it was about time we had to use them because there were so many more things you can do with less code, and they were so fast and fun to use.

(Source: YouTube.com)

Athene: What do you think about List Comprehensions, George?
HotShotGG: I THINK IT'S AWESOME! IT'S FAST, IT'S FUN.

Also, before I forget (new list comprehension functions we encountered in the lab):

Filter is a function of list comprehensions that evaluate an iterable (had to use tuples for this in lab), that applies the function to each item in the iterable and eliminates all elements for which the function evaluates to False.

Zip takes two lists, and pairs the ith element together from each of the list and turns it into a tuple. The tuple then gets appended to its own list and becomes the ith element of that list. (remember you have to assign it to a variable so you can call it again.)

P.S.:

Pre-Order = Root first > Preorder left subtree > Preorder right subtree

In-Order = Left subtree first > Root > Right subtree

Post-Order = Right subtree first > Root > Left subtree

ONE LAST THING THAT CONFUSED ME THIS WEEK:

And I finally understand after some example code testing:

You can concatenate values onto a list if the first value in your ([a] + b + c) expression is a list. O:! I was wondering why some random line of code with all plus signs was returning a list then I found the magic [] brackets for a list ._. ...

P.P.S: If you're looking for a TL;DR, sorry this is already a tldr version of this week >_<

Week 5

Hi again! :)

The tip of the iceberg is what I would probably call this week. The little bit of recursion that we have learned so far, we are putting into use. In the lab this week, pretty much every single exercise was recursion-based.

In my opinion, I thought it was rather exhilarating when I finally figured out how to code something, when I finally grasped the idea and the light bulb flicked on in my brain.

From what I have come across in this lab and the lectures, I will share what I think is the key to recursion for those of you who are reading this and feel like you're struggling with it (so far...I'm pretty noob too, but this is from noob to noob ;) ). I feel like the one most essential thing in recursion is to always call the function itself in its own function body, and it will call and call again until it reaches a base case, in which case the result will be evaluated. I felt like once I grasped that detail, everything kind of fell into place. An epiphany if you must.

Anyway, I'll edit this again after Wednesday's lecture and after doing some work on assignment 1. :)

EDIT: Well the global, local and nonlocal stuff was confusing, going to go play around with the example to try to understand it. Although I found the parent class things to be relatively easy to understand.

P.S. List comprehensions save lives.

SEE YOU NEXT WEEK!