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.