Recursion and Binary trees

This week, the definition of tree is introduced in class, which includes the definition of several terms such as leaf(node with no children), internal node, subtree, height of a tree and so on. Then, the three kinds of orders to read a tree are also introduced, including the preorder, postorder and inorder.
In order to present the value of each node with the given order, some recursion methods are used to reduce the work load, such as preorder can be represented as [tl[0]] + preorder(tl[1]) + preorder(tl[2]), which can be find out by listing several examples based on the given tree. 
Moreover, the way to present inorder is inorder(tl[1]) + [tl[0]] + inorder(tl[2]) and postorder is postorder(tl[1]) + postorder(tl[2]) + [tl[0]]. For each of the tree, a list with either int value or list can be used to present trees, such as [5, [4, None, None], [3, [2, None, None], [1, None, None]]], where None represents no children for the nodes with value that is in the position index 0.
Since the tree is also a kind of ADT, we can create several methods such as check whether a value is contained in the tree by creating a method __contain__ and so on.
One thing that needs to pay attention is that when writing the codes with comprehension, sometimes we need to write "()" and sometimes a list is needed. To provide an example, when using the function sum to find the sum of the given numbers, we need to write sum([numbers]) instead of sum(numbers) since it can sum up the numbers in the list but not the single numbers. Furthermore, writing a square bracket is also necessary when the comprehension is complicated.

-Flora

Nested functions and recursion

This week we discussed about the nested function and more example about recursion. And the Hanoi tower of three stools is introduced as new knowledge.
The code is like this:
       three_stool(model, number_of_cheeses - 1, origin, middle1, destination)
       model.move(origin, destination)
       three_stool(model, number_of_cheeses - 1, middle1, destination, origin)

When I try to trace the code above, I find the total steps are nearly 300, which is impossible to think how each step works. However, when thinking it by using another way, it becomes pretty easy. We can just treat the function three_stool as a move method and put the original stool, intermediate stool and the destination stool without thinking anything else.

Also, I got an idea about how nested function works, which shows that it only works inside the function we defined previously and we cannot use it independently by calling a(), where a represents a nested function inside another function.
The new idea about recursion is that we do not really to trace the step one by one but try to understand what steps are repeated when running the function. As we trying to solve the problem, a base case is needed to develop the whole. Since the base case plays an important role in developing the whole recursion, it is very important to find a correct one and write the return statement in order to produce value in each of the step in the recursion function.
To talk about the assignment one, I used to find the value of i by using the recursion method but after trying some actual example, I find it difficult to find a base case for the recursion function. Therefore, I used for loop instead of the recursion method, which means use the function          
 temp_moves = 2 * best_moves[n - i] + 2 ** i - 1
to find out the i that produces the least number of moves.

Finally, good luck for the following week!

The forth week's report

This week we continue discussing the examples of recursion, which is an amazing and efficient way to solve problem. For example, we can use it to find the depth of a list with several codes and if using the normal way instead using recursion, it will be very annoying due to the 'huge' work. The turtle recursion that is discussed during class is also an example. After tracing the code in the example, my friend and I find we can hardly write the code without recursion, however, the way to write codes such like this takes some time to think about...maybe exercises help a lot.
Now move on to the assignment 1. I nearly finish it although at the beginning I find it really difficult and hard to understand the meaning of it. The fact is, we should try to read and understand the meaning of each function and each module that are provided. At first I think it is ridiculous that the headers are worth 50% percent of the total mark. But later on, it is proved that the headers are quite important and if you can write down all the correct headers, it means you understand nearly 80% of the assignment 1. I am trying my best to finish the last step as soon as possible and discuss the best solution with my partner as well as the bonus question.

- Flora