Week 5  Tracing Recursion

This week we learnt recursion, which is a topic I never met. At first, I raised the same question with Ji Yong Chio(http://148choi.blogspot.ca): why we do not just use for loop or while loop to execute the repeated operations? Chio thought that because recursion has less running time. However, I hold a different opinion. Recursion can solve more complex problems than the for loop. Just like the example in the lecture, for nest of

nest of nest list ([1,2,3,[4,5,[6],7],8,9]), if we want to sum every number in the list, recursion is best way to do this. It can continue simplifying the list until the integer number and then sum it up. Therefore, recursion is able to solve any type of list in spite of its depth. Nevertheless, for loop can only deal with one depth, through for loop, we cannot get the expected result: 40. Furthermore, I checked the concept of recursion in Wikipedia: “recursion is the process of repeating items in a self-similar way.”(http://en.wikipedia.org/wiki/Recursion) After seeing the applications and instances in the computer science and mathematics field, the scattered pieces of concept became a clear map to me.

 

When it came to trace recursion, I feel a little bit confusing and messy about the tracing process. I could keep the professor and myself on the same page in the lecture, but when I practiced alone, I always made small mistakes. Fortunately, I found the pattern after listening TA’s advice and doing a number of practices in the lab. Tracing recursion without docstring was extremely helpful to me to understand the process and meaning of the recursion. To figure out this problem, the first step I did was to focus on the operation “else #if L is not a list”. And then plugged this into the recursion step “if isinstance(L, list)”. For instance:

And I made a summary to varies kinds of list recursion:

1) Count the number of items in the list

2) The sum of all the items in the list

3) The depth of the list

4) The maximum number among the length of list and its sublists

5) The total number of list and its sublist

The biggest hardship I encountered was writing recursion myself. I found a stupid way to overcome, that was, used for loop first, and then transferred it to recursion approach. Take a problem in lab, for instance:

First:

And then transfer into recursion:

Although this approach is more complex, it seems work good to me. I will do more practice to get familiar with this process in order to write the recursion code directly and precisely.