Slog 8

week9's topic is about inserting on Binary search Tree. To begin with, Binary search tree is a very special abstract data type, because the data in binary search tree is sorted. To be more precise, numbers on left children nodes are always less than their parent nodes and numbers on right children nodes are always greater than their parent nodes. Therefore, it makes easier for computer scientist to insert numbers into binary search tree. Firstly, we need to compare the number we want to insert with the number in the parent node, if the number is less than the number in the parent node, we will insert our number at the left hand side and running recursion on it, otherwise right hand side. As a result, it reduces the running time of inserting function and it will be a very useful method in the future.

Slog 7

week 8's topic is about linked list, which is another abstract data type. To begin with, linked list has some similarity to tree, which are linked is also contract by numbers of node and it is used to store data. However, the construction of linked list is different from tree. Firstly, instead of left and right children, linked list has front and back nodes. To be more precise, self.front refers to the entire linked list. In addition, self.nxt is needed to implement in order to have accesses on the next node. In conclusion, linked list is also one of the most important abstract data type in the study of computer science.

Slog 6

week7's topic is about binary Tree. Binary is a little bit different from normal tree. Firstly, instead of multiple of children nodes, binary tree only has two children nodes. To be more precise, it only has left children node and right children node for each nodes. Moreover, binary search tree is more useful than normal binary tree. In binary search tree, each left children is smaller than their parent node and right hand side children is greater than their parent node. Therefore, it makes easier for computer scientists to manage their data, and it also makes sorting faster. In conclusion, binary Tree is a very useful abstract datatype.

summary of Recursion

The Trace of Recursion:

Recursion is one of the most important methods that I learned in CSC148. To begin with, the fundamental process is to understand how recursion works. Precisely, we begin from chasing easy recursion. For example from the lab handout 3:

def count_elements(L):

    ’’’(list or non-list) -> int

    Return 1 if L is a non-list, or number of non-list elements in
    possibly-nested list L.

    ’’’

    if isinstance(L, list):

        return sum([count_elements(x) for x in L])
    else: 

        return 1 

We should start with the most base case, which is when input is not a list, such as 'hello', therefore, it returns 1 as result. Moreover, we should consider short list as input, for example, [1,2]. Because [1,2] is a list, it satisfies the if statement, therefore, it goes into the for loop which gives us 1 and 2 as input, and then we plug in 1 to the if statement, which returns 1, and so as 2. As a result, we will get a list of [1,1], and the sum of [1,1] gives us 2. Furthermore, we try more complex example, and we eventually convince ourselves that this recursive function returns the number of element inside a list. 

The Use of Recursion:

Recursion is frequently used in Tree, because tree is built with parent nodes and children nodes, and we need to search deep in children nodes to find data. Therefore, it is significant to use recursion to do the search repeatedly. For instance, this is one of the tree function in lab 05:

def list_all(t):
    ''' (Tree) -> list

    Return a list of values in t.

    >>> t = Tree(0)
    >>> list_all(t)
    [0]
    >>> t = descendents_from_list(Tree(0), [1, 2, 3, 4, 5, 6, 7, 8], 3)
    >>> L = list_all(t)
    >>> L.sort()
    >>> L
    [0, 1, 2, 3, 4, 5, 6, 7, 8]
    '''
    if len(t.children) == 0:
        return [t.value]
    else:
        all_list = [t.value]
        for c in t.children:
            all_list = all_list + list_all(c)
    return all_list
This is the completed version of the function list_all. However, there are three steps we need to do in order to finish this function. Writing out the base case is alway the first thing we need to do. In this example, we are asked to return everything in the tree. Therefore, the base case will be if there is none children in this tree, and we can just return its root. Second Step, we need to consider the typical case of this function. Thus, we assume it has one child node, which is 2. And then, the function in the else statement will be changed to all_list = all_list + t.children. In general, we have more than one child node. As a result, we should assume recursion works and apply it into the else statement.

In conclusion, the fundamental concepts of recursion are to write out the base case for the function, and then writing down the special cases with a short example, in the end, applying recursion base on that. However, it is complicated to trace recursion, therefore, we need to work on easy case and prove it works, and then assuming it works for the entire function. Recursion is a very important and useful method that we need to understand in order to solve problems in CSC148.