Week Seven - Recursion

Week Seven - Recursion

Recursion is very powerful programming technique, in recursive functions, the function will call on itself in its function definition (recursive call). Since the function has to stop and return at some point (or else, if the function just keeps calling on itself, a RuntimeError will occur saying maximum recursion depth exceeded ), that point where the function itself is no longer being called is know as the base case. In this sense, recursion is very similar to induction in mathematics.
Recursion works well often when a big problem can be broken into the small version of the same problem. For example, in A1 the way to move cheeses using 3 stools is a recursive function because as long as n is greater than one you will be doing the same moving strategy: first move n-1 cheese to the intermediate and everything to destination. You will be keep calling this function until you get to the case n = 1, where there is only one cheese, then you will simply move this cheese from the source to destination. Recursion is also extremely useful when you want to do operation on a nested list or any other recursive data structure (consist smaller instance of themselves), i.e Trees, LinkedList. In class we did the example that returns the sum of a nested list, the same task can possibly be achieved without recursion, but the code would be much more complicated to write. Recursive structure is also possible to optimize efficiency, for example in the week six lab, we implemented the class Queue using the recursive structure LinkedList. When the Queue is implemented correctly, as described in the handout, when run the testqueue.py it will take the same time no matter how many element is in Queue.  However, when we implemented the class using list, the run time growths and more elements are added.
I also want to also say that although recursion is a powerful method, it should be avoid in some cases:
consider the following methods:
def sum_up_to1(n):
    """
    return the sum from 0 up to n using for loop
    """
    sum = 0
    for i in range (n+1):
        sum += i
    return sum
        
def sum_up_to2(n):
    """
    return the sum from 0 up to n using recursion
    """    
    if n == 1:
        return n
    return n + sum_up_to2(n-1)
I used a timer to test the efficiency of those two functions. To add up to 500, the first method took 0.0s while the second one took  0.000999927520751953s. One thing really interesting is when I did sum_up_to2(1000) it raised a RuntimeError saying the maximum recursion depth exceeded in comparison, while sum_up_to1 still took 0 second. I think it is because you need to call on the function too many times to get to the base case, and the computer just ran out of space. So, if there is not a nested structure and loops can be easily applied, you might not want to use recursion, as it might takes much longer as shown in the example above

Week Five - Trees

Week Six - Trees

I believe the most important thing beside the lecture this week was assignment 1. So I wish I could spend some time talk about that first.. At first, the assignment looked very complicated - three pages of assignment sheets, five files, hundreds of codes and the codes in GUI files were not making any sense (I later discovered that it is totally unnecessary to understand the GUI files to do the assignment). However, as I started to with through the assignment step by step with my partner, it was surprisingly not that bad. The first three steps were almost review from CSC108 (i.e. choose a data structure, write method for class). The fourth step required some knowledge with exception, however, in my point of view, exercise 2a and 2b really prepared us in order to complete this step. Step 5 is the hardest step in assignment 1, the method of moving three cheeses we discussed in class, and the hints in the assignment sheet really helped us a lot. Me and my partner first thought i is simply n//2 (it worked fined with the n<7). However when we finished implementing the whole method in Tour, we manually calculated more minimum steps for greater number of n, the theory fell apart. So we decided we are going to try all values of i from 1 to n-1 (using a for loop), and compare the number of steps associated with each i. The i with the minimum step among all i for a particular n will be the "i" we want. Since the algorithm involved a lot of recursions, it took so long to run as n becomes bigger. But, the method worked fine (although it is probably not the most efficient way of implementing it).


This week in class we implemented a class called tree, and it is through recursion. I think now we are moving the problem from tracing and understanding recursion to actually writing recursive codes ourselves. Since everything will break down eventually to a base case, I found it much more helpful to think about the base cases first. I think I really got a better understanding on recursion after assignment 1, so this week's lecture material was fine for me to understand. However, I do wish to include two Python build-in functions here, I think they can be really helpful on list comprehensions:
filter(function, iterable):
Construct an iterator from those elements of iterable for which function returns true.
any(iterable):
Return True if all elements of the iterable are true (or if the iterable is empty)

Finally, in the lab this week, there is one part that you have to convert a list comprehension to a for loop, I think it would be a better exercise, if it had been the other way around. Because we are much more familiar with writing a for loop, than a list comprehension.

Week Five - Scopes and Namespaces

This week's first lecture was about how to solve the cheese problem using only three stools. I am really happy that the solution was discussed in class, because I think it would be much hard if I was to trace and understand that recursive code myself. After the lecture on Monday, I finally fully understood the four-stool algorithm described in the assignment sheet. 

The second lecture was about scopes and namespaces. I really enjoyed the topic and we did some really interesting examples in class. One thing I found Java very special is that everything is a reference to a memory address somewhere in the computer. Surprisingly, it is also possible for two module to have the same function name. But if both module is imported by the user, and if he/she wants to use the method, they must prefix it with the module name. In the lecture, we also talked about how to search for names: it will first look in the inner most scope (e.g. if you define a function inside in a function, python will first look in there), then it will look in the enclosing scope, then the current module or __main__, finally it will look in the build-ins. If they can't find the name in the build-in, an error will be raised. A name can also be declared nonlocal or global and if you don't put anything infront of the name, it will be local (which is the default). Finally, the example we discussed in class was quite tricky, I would probably did most of it wrong if I was tracing it myself. Namespaces and scopes is a new topic, I think I need to spend more time on the concept in order to grasp the concept.

The lab this week is about recursion, the handout first asked to trace two recursive functions. I found that pretty helpful, because I knew how to trace it in my head, but I was unsure the format of writing it down on paper. The programming part of lab went surprising well this week, me and my partner figured both method out. And we even tried some extra problems. I think I am improving in writing recursive functions, but I still need more practice to master recursion.