Week 5: My impressions of tracing recursion from Week 4

          When I was first introduced to recursion, I could not comprehend the code. The reason was that I had never seen a function that implements itself within its own code before. And when I was asked in class to trace a recursive function, I failed to do so step by step. Fortunately, my confusion was cleared when professor Danny taught the class step by step regarding tracing recursions.

          In order to show my gradual process of ultimately understanding the concept of recursion, I will begin with a recursive function as an example: 

(Note: this function is taken from additional exercises from Lab #3)

Now, I will trace all four example calls and explain my thinking as I go. 

          To begin, I will trace count_lists([2, 1, 3]). When the list [2, 1, 3] is being inputed into the function “count_lists”, the first “if” is evaluated. Since [2, 1, 3] is indeed type list, the “isinstance()” method is evaluated to True, and the statement “return 1 + sum([count_lists(x) for x in L])” is next to be implemented. Now the trace looks like this:

count_lists([2, 1, 3]) —> 1 + sum([count_lists(2), count_lists(1), count_lists(3)])

This is because the list comprehension applies the function “count_lists()” to every element in list [2, 1, 3]. Since 2, 1 and 3 are non-lists, the “isinstance()” evaluates to false and the code under “else” gets executed instead. As a result, sum([count_lists(2), count_lists(1), count_lists(3)]) becomes sum([0, 0, 0]). Hence, after simplification, the entire trace process will end up looking like this:

          Next,  I will trace count_lists([2, 1, 3, ‘[4]’]). Now, the tricky part of this trace is that ‘[4]’ is type str not type list, hence count_lists(‘[4]’) will return 0 just like the other three ints.

          The previous two examples were really simple and I had no problem understanding them. However, the next two example calls are a bit more complicated to trace since it involves inner-lists. 

The hardest part to understand would be the second line. Hence I will rewrite the first line into this:

1 + sum([count_lists(7), count_lists([2, 1, 3]), count_lists(9), count_lists([3, 2, 4])])

Since 7 and 9 are non-lists, count_lists evaluate to 0. However, because the second and fourth elements are both type lists, count_lists will evaluate to 1. One thing to notice is that count_lists([2, 1, 3]) and count_lists([3, 2, 4]) are simple recursions like example call 1. Since we have traced example 1, there is no need to rewrite it for this example call, and we can simply write 1.

          The last example call is the most complicated of the four. Fortunately, we can skip some intermediate steps when tracing since we did similar ones in the previous three examples. Looking at the example call, I can quickly spot that evaluating count_lists on element 7 and 9 is easy since they simply return 0. Furthermore, because we traced example call 1, we know that count_lists([3, 2, 4]) returns 1 + sum([0, 0, 0]) and hence 1. The most difficult part is evaluating the second element in the example call, since it contains an inner-list within an inner-list: [2, 1, [3, 4], 5].  This is the part where I had trouble the most. In order to fully understand this example call, I decided to break it down into simpler parts. I have already evaluated the first, third and fourth element, thus, I will simply trace count_lists([2, 1, [3, 4], 5]):

Now that I have evaluated the example call by breaking it into simpler parts that I have traced before, I can combine my solution:

          In conclusion, my initial reaction to tracing recursion is confusion. However, after patiently tracing all the practice exercises, I can confidently say that I have understood the concept behind recursion and if I am given a recursive function, I can easily understand its purpose by tracing several example calls. Although recursion requires more memory than iterations and it is slower to run in general,  it is nevertheless useful. The reasons are that:

1. Recursion presents a more elegant and succinct code for implementing a variable number of    nested loops, since the code usually only take up one line 

2. Recursion reduces time complexity 

3. Recursion makes tree-related coding simpler 

Therefore, I find recursion to be a very interesting topic to learn, and I hope that I will get some practice on writing recursive functions. I have a hunch that recursion is going to play a very important role in Assignment 2.