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.

Week 4: Recursion and nested list

This week we learnt how to find the depth of nested list in a recursive way. It is the first time for me to learn recursion, it seems much more simple than for loop or while loop, because its results are always very short, maybe in one or two lines. But it is hard to figure out how it runs for me.

Let's look at an example first(which we learnt in class):

All recursion need a base case and a recursion step.

What I think difficult to do is to build the recursion step, it is really hard for me to find the relation ship between the base case and the current case. I was struggled for a long time on e2.

But fortunately, one of my friend taught me that I shouldn't think too much on the whole procedure, just figure out the relationship by simplify the current cases.

I did so, and was surprised to find I am done, I made it. It is no doubt that recursion is not that difficult, just analyse in a right way, every one can grasp it.

Week 3 : About Object-oriented programming

In Wikipedia, the definition of Object-oriented programming is showed below.

"Object-oriented programming (OOP) is a programming paradigm that represents concepts as "objects" that have data fields (attributes that describe the object) and associated procedures known as methods. Objects, which are usually instances of classes, are used to interact with one another to design applications and computer programs.[1][2] C++,Objective-C, Smalltalk, Java, C#, Perl, Python, Ruby and PHP are examples of object-oriented programming languages."

It has a series of basic theories, like class, subclass, method and so on.

Just as we learnt in Python, a class is defined as "an extensible template for creating objects, providing initial values for state (member variables) and implementations of behavior (member functions, methods)".

For example, we defined two classes as Toy and Dog in the exercise we did before. We made 'Bob = Toy()', then Bob belongs to the class 'Toy', it has the implementation of behaviour 'play',which means it can be 'play'ed.In the example above, we can also define other two things as object and method. 'Bob' is one of the Toy, it has its own properties, by which I mean, it is unique over the world, and we call it 'Object'. Maybe 'Bob' have many common properties with other 'Toys', but it is itself. Different from the abstract 'class', it is a specific concept. Just like 'class' is a set of all things around the world containing some things which have similar properties, but 'object' is the particular element in the class. As for the 'method', it defines many things that 'objects' in 'class' can do(but not have to). Let's back to the example above, all 'toys' have the 'method' play, if we make 'Bob.play()', it will return 'Squeak!\n'.

These are the basic definitions in the OOP.

I think it is a very convenient way to create a new class, for dealing with problems more specifically and easily.