SLOG #4: Trees

Last week, we didn't learn anything new. However it's still very helpful since we applied knowledge from before, especially recursion, to build trees. A tree is a good example of a recursive structure.

We firstly learned some terminologies about trees and found there are three different ways of traversing a tree: preorder, inorder and postorder. It's quite useful to learn how to write functions for these traversals. I found these functions are the same in base case. The only difference is the order of the functions in general case. The advantage of applying recursion is obvious here because it is easy to read what is going on in the function.

Code for general tree implementation is a little bit hard for me to write at the very beginning. After Professor Danny showed us the answer, I felt things become easier and I started to get used to the tree structure. Through practise, I feel it's efficient to think about several easy examples, write down the base case carefully firstly and then to introduce it to general case.

The midterm is coming next week. Good luck everyone :)

SLOG #3: Towers of Hanoi and Namespaces/Scopes

I spent most of time of this week working on the first assignment "Tower of Hanoi" which was really challenging. I was inspired by the hint given in class about how to move cheeses of three stools and finally figured out how to use the same recursive logic on four stools. This assignment definitely improves my programming ability and my understanding of recursion. I was quite excited about the animation of my solver when it automatically solved the puzzle using computer's amazing calculation speed.




I felt quite confused about the concept of namespaces and scopes learnt this week. I didn't know exactly how local scope and global scope work at the very beginning. By reading the scopes and namespaces from the python official website, I got Python searches for names in order from local scope, enclosing scope(nonlocal), global scope to built-in scope.  We could add nonlocal assignment to change scope_test's binding and global assignment to change the module_level binding. These assignments are quite useful when assigning values to variables.

Finally, I have a question:

Context A:

>>> x = 'outer'
>>> def func():
 print(x)
 x = 'inner'
 print(x)

>>> func()
Traceback (most recent call last):
  File "<pyshell#6>", line 1, in <module>
    func()
  File "<pyshell#5>", line 2, in func
    print(x)
UnboundLocalError: local variable 'x' referenced before assignment

context B:

>>> def func():
 print(x)

>>> func()
outer

This example is from: http://docs.python.org/2/faq/programming.html#why-am-i-getting-an-unboundlocalerror-when-the-variable-has-a-value

It’s really interesting to see I can’t reference x in the local slope that is assigned in the global scope before assigning it in the local scope (context A), however it works without assigning it in the local scope (context B).

Feel free to leave comments here. I hope to learn more from you.

SLOG #2: Recursion

This week we learned something about recursion which is really efficient for solving large-scale problems. Recursion means “defining something in terms of itself”. This approach breaks down a complex problem into small pieces which we could apply the same algorithm to with changing parameters until a termination condition is reached and combines the result.

Every recursive function is a combination of general case and base case. Base case is also called termination case. Every recursive function must have at least one base case otherwise it will keep calling itself. The general case is a recursive sub call which happens most of time. We should avoid leaving out the base case when writing a recursive function as well as circularity.

We could use both recursion and iteration to solve problems involving repetition. Compared to iteration, recursion is easier to read and requires fewer lines of code; however it is a little bit slower. This is because recursion calls itself many times and stores certain values on the stack for each function call, which takes time and stack space.

Finally, feel free to leave comments here J