More On Recursion/Trees

The week leading up to the midterm has been focused on a new ADT named Trees. Though we have yet to see any major application of trees other than LinkedList (A tree with arity one), the foundations have been very well laid out. In its essence, Tree in python is a form of data structure that contains numerous data of the same structure that can contain even more pieces of data. An intuitive way to understand this data structure is through its name as observed in nature. A tree has a source where its branches can grow, and on each branches there can either be leaves or more branches and it goes on in this way forming the entirety of the Tree. In programming, the joints in which the branches grow are called "nodes" and the branches that grow from it are the "children" of the node, and the nodes at with no further branches are, naturally, "leaves". Since these Tree contain information that are very much like itself, a very natural way of defining a Tree structure is via recursion. To initialize a Tree, we define it's node with a value, and go on to define it's branches which can either be None by default, or another Tree structure, and eventually reach Trees with value at the node, but no children. A tree's children is represented as a list containing more Trees, the reason for this is, perhaps, for an easy access to each children Tree through the indexing of the list. Here we can see another benefit for recursion being that it is a natural way to define objects with fractal-like property. Not only is recursion used in the initialization of the Tree class, it is used in various method for its properties as well such as arity, height, number of leaves. The implementation to find all of these properties for a tree requires a recursive function until it reaches the bases case, the trees that do not have anymore children.  For example,  to find the number of leaves in the a tree, the easiest way and the cleanest way to do so, is to create a recursive function that goes to the children of children trees until one reaches a Tree without children then add one to the total number of leaves. Also, list comprehension is used in these functions as well to find things such as the sum, minimum and maximum. Overall, it seems that CSC148 is using what we learned in previous weeks cumulatively to introduce us to more complex concepts, in the near future I hope we can see how using the recursive structure of trees can be used to solve practical problems. Thanks for reading.