Regular Expressions

For assignment 2 we have been tasked with working on regular expressions, and regular expression trees. Since I hadn't really heard anything about regular expressions I decided to do some Googling before I began. Turns out, regular expressions are quite useful. They allow for matching a variety of strings by simply using the correct expression. There are different types and different languages that use regular expressions but they are generally used in similar ways. They can be extremely useful for pattern matching; for something simple like looking for whitespace or even full sentences.

I spent some time struggling with the first function that I was working on: is_regex() – which determines whether or not a string is a valid regular expression. It is of course a recursive function and really doesn't seem that difficult at first glance, but there are some cases to consider which take a bit more work. The challenge is basically to determine the proper amount of nesting for parentheses inside a string. I tried a couple methods which worked on some test cases but not all of them. I ended up using a helper function to get what I needed done and it seemed like a pretty clear solution so I'm happy with that.

I'm not very far into the rest of the assignment so I better get to that and update about that next week!

Programming in the wild...

This week we had an exercise on building trees, as lists from their nodes in a certain order, and finding the sum of the 'deepest' leaf. I found this to be the first exercise that I would describe as quite challenging. I'm not sure if it was because of my lack of knowledge about the techniques or a lack of programming intuition but I definitely struggled with the two functions mentioned above.

I can't help but wonder if this is what programming in 'the wild' will feel like. Encountering something that wasn't just designed to be worked through as an exercise or assignment, but a real world problem that might not actually have a solution until I come up with one! It's kind of scary but at the same time exciting to think of being able to tackle these types of challenges.

In the end, after I devised a solution, the functions weren't actually all that complicated looking. Although, when you're sitting at the computer just watching the cursor blink it seems like the solution might allude you for all eternity.

Without saying too much about the solutions to the problems; if your looking to build a tree from an ordered list – slice it up! If you're looking to do something to the values in a tree – keep track of them during recursion!

Recursion part 2

Recursion is: see previous post on recursion. No really; In a nutshell that's recursion! Recursion is having faith that a problem has already been solved and letting it solve itself using that knowledge.

Ok, so there's a little more to it than that but since I had already made a post involving recursion, it seemed appropriate to define it that way. Recursion is a very powerful tool in any programmer's toolbox.

When a recursive function or method is executed there is generally a condition to be met or a check to determine whether the recursive case or the base case should be executed. If the recursive case is needed the function calls it self, and stores the calls in memory. This continues until all that's left is the base case. Then the base case is resolved. Once this happens, all the previous recursive cases can then be resolved with respect to that base case.

The reason that this is so brilliant is because a lot of problems actually turn out to be the same problem wrapped up within themselves many times. This variety of problem can seem quite large and daunting when viewed as a whole. However, the power of recursion allows for a very useful way of modelling such a problem.

A common example of recursion that many people will have seen is factorials in math. Each time a factorial is increased, it becomes the product of the new number and the previous factorial total. This is a recursive structure because each factorial can be broken down in such a way.

At first I struggled with the concept of recursion, but being exposed to it repeatedly has greatly helped my comprehension. The weekly labs in particular have been a great opportunity to learn recursion with the help of peers and teaching assistants.