Week 7: Recursion!

The main focus of this course so far has been on the recursive technique. Recursion is a computer science technique, where in order to solve a problem it is required to solve smaller instances of the same problem. Recursion involves writing a function whose code includes a reference to the function itself; in other words, it involves functions that call themselves to solve smaller subproblems.

The recursive technique, as we have seen in lecture, often consists of a single return statement, which is usually a list comprehension with two separate parts: the base case and recursive call. A list comprehension allows for the creation of a new list through iteration within a single line, making the code much more concise and understandable. The base case is the instance of the function which does not lead to a recursive call; this is probably one of the most important elements of recursion, as without it, the function would consist of infinite recursion; in other words, the program would cause the function to continuously keep recalling itself until it crashes. On the other hand, the recursive call part of the return statement includes the reference to the function itself, under a specific condition of an if statement.

Among many of the examples of recursion we saw in lecture are methods involving the classes Tree, LinkedList, and Turtle. We have also seen recursion on nested lists, such as the function sum_list, which takes in a nested list of numbers as an argument and returns the sum of all of its elements.

An advantage of utilizing recursion is the fact that sometimes it is the only way of solving certain very complex problems. By breaking a very complex problem into smaller, simpler cases, the problem suddenly becomes much easier to deal with. Moreover, the code can become much more elegant and sometimes even more straightforward through the use of recursion.

On the other hand, a disadvantage of the recursive technique is that when processing an extensive instance of the problem which requires a very large amount of recursive calls, the operation might cause a StackOverflowException leading the program to crash.

Overall, recursion is very useful, but sometimes it should be avoided in particularly simple problems in order to prevent Pythonistas from overcomplicating the code.

Week 6

During this week, we learned about the concept of trees. Trees are Python objects that consist of two sets: a set of nodes and a set of directed edges. One of the nodes is distinguished as the root; it is defined as being the only node with no parents. On the other hand, every non-root node has exactly one parent. While leafs are defined as nodes that have no children, internal nodes, on the other hand, are those that contain one or more children.

Paths can be formed between certain nodes in a Tree. A path is a sequence of nodes n(1), n(2), ..., n(k), where there is an edge from n(i) to n(i+1). The length of any path is defined as the number of edges in this path. A very important property of trees is the fact that there exists a single, unique path from the root to each node in the tree. For example, in the case of the root itself this path is just n(1) (if the root is n(1)), with length zero.

Another very important property of trees is the fact that paths cannot form any loops. The height of a tree is the maximum path length in a tree. Trees with a height of at least one contain subtrees, which are trees formed by any tree node together with its descendants and the edges leading to them. The arity of any specific tree is defined as the maximum number of children for any node in that tree.
During lecture, we wrote specific functions for the trees, including pre-order, post-order and in-order.

Moving on to a different subject, in this week's lab we were expected to transform list comprehensions into loops over iterables. In my opinion, this was a particularly straightforward task, and my partner and I were even able to finish the lab early for the first time since the beginning of the semester!

The last new thing we learned about this week were the two list comprehensions any and all. The first one can be applied to a list to check if any of the elements satisfy a given condition, while the latter can be used to get the bool of whether all elements inside the list satisfy a specific condition. These are particularly useful in order to write shorter and more comprehensible code, which is always more efficient!

Week 5

Throughout this week, we have been dealing with deeper recursion problems as well as learning about the hierarchy of name and method searches. I also began working on Assignment 1 in the beginning of the week, and finally finished it a few days ago.

Assignment 1 deals a lot with class definitions and methods, as well as recursion. When I first looked at the code for GUIController.py, ConsoleController.py and TOAHModel.py, I was startled. I did not understand most of the code in GUIController.py and was really confused as to how to start the assignment. However, after following the first two steps in the assignment handout, I created the method header and code for each required method, and was pleasantly surprised when I ran GUIController.py to play the game manually and it worked! On the other hand, I thought ConsoleController.py was particularly straightforward and finished it quite quickly.

The challenge, however, lied in Tour.py, where we were expected to write the recursive function that would move a tower of cheeses from the first stool to the last stool with the highest possible efficiency. I found this particular step in the assignment especially hard because I could not find a way to optimize the choice of i. After a lot of brainstorming, writing equations on pieces of paper and searching to understand the problem, I believe I derived to right function for finding i, which seemed to work for all numbers. From then on, I finished the assignment fairly efficiently and was extremely excited when everything worked!

The lab this week dealt even more with recursion problems. We were expected to write tons of recursive functions, and then modify them further until they were very efficient. I was actually surprised to find out that I understand recursion pretty well. By tracing each step on paper first, writing the code seemed particularly straightforward afterwards. My partner and I were able to finish all functions and we were even able to work on the bonus exercises.

During lecture, we learned about the hierarchy of searching for names and methods in Python. When a Pythonista refers to a name on Python, the program first looks in the innermost scope, called the local scope; this scope usually consists of the function body. If it does not find such a name, it goes on to look at the enclosing scopes, called nonlocal; these usually occur when the referral to the name occurs in a function within other functions. Next, Python looks for the name in the current module __main__, referred to as global. Finally, if it does not find the name in any of the previous places, it goes on to see if there are any built-in names with the same name. If it does not find the name in any of these locations, an error is generated.

When a method is called, the process is similar to that of searching for names. First, Python looks in the nearest subclass and then it works its way upwards until it finds a method with such a name. Similarly, if Python fails to find this method, it generates an error.

Week 4

During this past week, we have been dealing a lot with recursion problems. In contrast to iteration, recursion, from what I understand, is a technique that involves the use of a function that calls itself in its code under certain conditions. That is to say, the function repeatedly calls itself until it is told to terminate; otherwise, the process becomes infinite and will generate an error. Recursion is very useful for condensing long iterating functions into very simple, short recursion examples, as the ones we saw in class.

One of the examples of recursion we saw since the beginning of the course was in determining the number of layers in a nested list of numbers. The function we created in class calls itself whenever a nested list is found inside a list of numbers, allowing for the prevention of the use of never-ending if statements in an iteration.

The most interesting thing we learned this week, in my opinion, was the Python built-in Turtle class, which allows Pythonistas to draw different line diagrams through the use of turtles that can create lines of different colours, speeds, directions and lengths. In this week's lecture, we were presented with an example of a recursive function called 'tree' with the use of Python's Turtle class. The function created three times as many different turtles, each at 120° from each other, as its level increased. As the levels would go up, three additional turtles would be created at the tip of each turtle created in the previous level. This resulted in a diagram that looked roughly like a triangular tree, with three different colours.

During this week's lab we were faced with more problems involving class creations; however, this time we were also expected to test our code utilizing unit test. This was certainly the hardest part of the lab, since I was not particularly acquainted with how to test functions using unit test and I believe it to be very hard in comparison to doc tests. Unit tests are especially difficult in my opinion because they require us to write our own classes in order for them to test our code, which I believe is very confusing.

The most challenging task in this week's lab was having to modify our unit test classes in a way such that it saved us effort by using inheritance to prevent code from being written twice. I found this very hard, since all classes had slightly different unit tests, and thus my partner and I were unable to complete this task.