Week 7: Recursion

Recursion is a process, in which it repeats all the time until the base case occurs. It is a common application in math and computer science.

A recursive method shuould have at least two properties:
1.the base cases
2.rules that reduce all other cases toward the base case

It is useful to deal with a complex problem with countless cases. We can just simplify the complex cases into the easiest one by repeating the same method， just like peeling onions.

Another example of recursion in reality is that we put two mirrors face to face, and put a candle in the middle of them, then we can see countless candles in mirrors. It can be regarded as a recursion.

As for the Python we are learning, the Tower of Hanoi is a good example to understand.

For three stools, we have two base cases, and for four stools, we have three base cases. The "else" on the bottom is what we call recursive rules. No matter what case is given, it can always get to the base case, and get the wanted result.

On one hand, recursion can help us solve many complex problem, on the other hand, it is some kind of inefficient, for each process, it calls itself many times, so that it have much data to deal with until get the final result.

Anyway, from what we are learning now, recursion can be said as one of the most practical method.

Week 6: Binary Tree

This week we learnt about binary tree, which has three ways to be represented.

The first one is preorder.

def preorder(tl: 'TreeList') -> list:
    """
    Return list of values in tl in preorder

    >>> preorder([5, [4, None, None], [3, [2, None, None], [1, None, None]]])
    [5, 4, 3, 2, 1]
    """
    return [] if tl is None else ([tl[0]] + preorder(tl[1]) + preorder(tl[2]))

Second one is post order,like below.

def postorder(tl: 'TreeList') -> list:
    """
    Return list of values in tl in postorder

    >>> postorder([5, [4, None, None], [3, [2, None, None], [1, None, None]]])
    [4, 2, 1, 3, 5]
    """
    return [] if tl is None else postorder(tl[1]) + postorder(tl[2]) + [tl[0]]

The last one is inorder.

def inorder(tl: 'TreeList') -> list:
    """
    Return a list of values of tl inorder

    >>> inorder([5, [4, None, None], [3, [2, None, None], [1, None, None]]])
    [4, 5, 2, 3, 1]
    """
    return [] if tl is None else inorder(tl[1]) + [tl[0]] + inorder(tl[2])

Every binary tree can be represented in such ways, and if we want a certain binary tree, we only need to know the preorder list and in order list of that binary tree.

Week 5: Towers of Hanoi

This week we mainly did the assignment 1. I had to say, the first task for me is to understand what it means. Maybe because I was not native speaker or a person familiar with computer science, I couldn't even figure out what result we should get running the final file.

So at first, I was not hurry to do what we are required. I asked a mentor how to understand the whole assignment, what function is each file -- 'ConsoleController.py','GUIcontroller.py' and so on.

After struggled in so many files, I finally figured out what each file is for.