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.