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 :) !