Week 6 – Trees and Finishing Assignment 1

The recursive structure of trees allows their functions to perform the same action on each of their individual nodes and leaves as they do on the whole tree. This makes most functions and methods for trees recursive.

In the example we saw in lecture of the basic tree class, a tree had two attributes: its value and children. The value could be any object, but its children was a list of—well--more trees. This was what allowed the same actions to be done on both the tree and its subtrees, recursively, until it got to the leaves, stopped, and gradually made its way back to the entire tree. For instance, to count the number of nodes a tree had, one would count the initial node at the root of the tree and then add up the number of nodes of each child of the tree. Since each child was also a tree, one could use the same function to count the number of nodes for that child.

Other than binary trees, we looked at a type of unary tree called a linked list. A linked list had a head and a rest, and the rest was another linked list containing its own head and rest, and so forth. This made the linked list a recursive structure as well, and we could perform the same operations on each part of the linked list as the linked list itself.

Assignment 1, which I'd started last week, will be due this week. It took me a long time to understand the GUIController and ConsoleController modules, because I was confused about the differences between the graphics of a cheese/stool and the object cheese/stool. That was before I took the time to read the docstring in GUIViewables, which cleared up that CheeseView actually inherits from the Cheese class and the PlatformView class to represent the cheese, so I only had to actually work with the Cheese class. After that, I progressed fairly quickly with the ConsoleController functions and TOAHModel functions. Finally, for the tour_of_four_stools function in Tour.py, I initially did not use recursion to find the value of i; I had used that the most efficient value of i would always be equal to the floor of n/2, with n as the number of cheeses, and just recalculated this value every time I ran through tour_of_four_stools. However, after learning that we were expected to use a recursive solution to find i, I rewrote a function to find i essentially following the formula given in the handout. Other than this, I found my A1 coding process to be a generally smooth one.