Week 7: Recursion Cont'd

Since I have already made a blog post about recursion, I will add onto it the new material we have covered in class. As mentioned briefly in the previous post, recursion is very useful in ways such as going through nested lists or loops. We were able to see this through our labs and lectures when we learned about classes such as LinkedList and Tree. In a Tree class, nested Trees are known as subtrees, and each node is a child. In order to create methods to count the total number of children in the Tree or calculate the height, it was useful to implement a recursive algorithm. For example, the code provided by the course uses recursion in the method count:

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

For me, recursion is very difficult to trace and I must write out each step of the function. This became a bit of a problem this week when during the term test the first question pertained to this exact topic. However, because of the amount of practice we had in labs, I was able to (hopefully correctly) answer the first question.

Speaking of the labs, I found this week's lab quite difficult when we were to add methods to the class of LinkedList. The first method that we worked on was determining the length of a LinkedList. The problem arose when we could not figure out a way to index a LinkedList, which would be useful in figuring out the length. We tried many different techniques; we tried to write while loops (while the second item in the list was not blank: LinkedList()), as well as trying to append each item to a regular list and determining the length of that list. By the end, we still could not figure out how to write this method, but in attempting different ways at tackling this problem, my understanding of recursion grew.

Week 6: List Comprehension

This week in class, we went over recursion a bit more when talking about tree lists with their nodes, which could be a root, a leaf, or an internal node. The recursive code occurs when calculating the height of the tree, or the number of children or leaves a tree has. There were many terms discussed in class pertaining to trees which were interesting, but something I found even more interesting since week one was list comprehension. List comprehensions are lines of codes that are read more easily, as if like a regular English sentence, which is why I noticed it since week one of this course because we were not used to this kind of coding in CSC108. They also shorten codes of multiple lines into one by writing both the 'if' statement and the 'else' statement in one line. When I first saw this kind of coding, it confused me and took a bit of getting used to, but the lab this week aided me in reading list comprehensions as we were to rewrite them in the structure we were used to. I may need a bit more practice with this way of coding, but in the end, it should be more efficient.

An example of list comprehension:
new_lst = [x**2 for x in origin_lst if x > 0 else abs(x)]

Recursion

Last week, we began learning about recursion and were able to implement this knowledge into this week's lab. We traced methods that used recursion such as one that converted numbers to their binary representation, but we also wrote recursive methods ourselves, such as ones that freezes lists. Through these exercises, I was able to better understand what recursion is and how it works. A recursive function is one which calls upon itself within the function. This is useful when trying to execute nested loops. However, one disadvantage of recursion as I am told is that it is much slower than non-recursive function, and can cause StackOverflow. Recursion seemed complex to me because it was difficult at first tracing the functions as it entered into nested loops, but because of the exercises we practiced with in our labs, I was able to better understand recursion.