Week 7 Slog

Hi, everyone!

The topic of this week is recursion. We have been dealing with recursion from the beginning of the semester. I think we can always see recursion in the lecture, lab and test. I have to admit that it is not an easy topic for me even it is not the first for me to approach recursion. It dates back the time when I was learning c++ and we spent lots of time on this topic. I can still remember the typical examples for recursion in C++ are factorial and Fibonacci Sequence.

The examples we have in recursion are quite comprehensive. At the beginning, we use nested list as our recursive examples. Then, we have turtle recursion and something called permutation, which costed me tons of time to understand what is going on. Additionally, we use recursion in our assignment and lab. I can clearly remember how we implement recursion in Hanoi Problem. Finally, we use recursion in Tree class and basically every method in Tree class requires recursion, which is quite challenging for us to write the code on our own.

I think the most efficient way grasp recursion to track some special examples and run the code in Python Visualizer. By doing this, you can really understand what is going on inside recursion. For example, if we write a recursive function to compute n!, then we have to go straight to 1!=1 and go back to n!. The prof mentioned the there's difference between human doing recursion and Python. I think if we are asked to compute 5!, then know the answer of 4! and then directly use it to compute 5!=4! * 5. Python does not know the answer of 4!, but it knows 1! and that is enough. It will go along back until reaching 5!.

When writing recursive function, I think what professor concluded about on recursion was very helpful. Basically, recursion involves a base (in order to stop the recursion)and a recursive formula. That is a good guide for me to write recursion function.

Finally, there's a recursive exercise in lab. We are required to reverse a string without using any built-in function. And following solution is really smart and reveals the elegance.  

def reverse(s):    
     if s == "":         
        return s     
    else:         
        return reverse(s[1:]) + s[0]