Tracing Recursion

Recursion, recursion, recursion.

This picture nicely sums up recursion. We were introduced to the topic of recursion in the fourth week, which in simple words means a function calling itself. Fortunately, I did not have much difficulty tracing the recursive code in class and therefore I believed that I had grasped this concept. I was so wrong. One example is not sufficient to grasp any concept then how did I foolishly believe that it was enough for recursion. This concept is fairly easy however requires a lot of practise in order for one to be fully confident about it. Recursion is like puzzle that challenges you and being the competitive person that you are, you will most likely say, “You are on.” I can't believe I just wrote that but you will understand that this is definitely as the case as I tell you more about this beautiful world of recursion.

We traced the following example in our class.

def sum_list(L):

'''

(arbitrarily nested list of int or int) -> int

Return the sum of all ints in L.

>>> sum_list([1, [2, 3], [4, 5, [6, 7], 8]])

36

'''

if isinstance(L, list):

return sum([sum_list(x) for x in L])

else:

return L

 

The function sum_list(L) returns L if it is not a list or it returns the sum of all integers in L.

Therefore, tracing sum_list(27) will execute to 27 because 27 is an integer and NOT a list.

Moving on, lets trace the following sum_list([4, 1, 8]).  Since L is a list in this case, we will perform the function sum_list on each of the item in L. Thus, sum_list on 4, 1 and 8. Then since these items are integers the function sum_list will return their value evaluating to sum([4,1,8]), which eventually evaluates to 13.  Below is a better representation of what I just explained.

sum_list([4, 1, 8])       -->sum( [ sum_list(4), sum_list(1), sum_list(8) ] )

-->sum([4 ,1,8])

-->13

Similarly, lets trace sum_list([1, [2, 2], [2, [3, 3, 3], 2]]).

sum_list([1, [2, 2], [2, [3, 3, 3], 2]])    à sum([sum_list(1), sum_list([2,2]), sum_list([2, [3, 3, 3], 2])])

-->sum([1,sum([sum_list(2), sum_list(2)]), sum([sum_list(2), sum_list([3,3,3]), sum_list(2)])])

-->sum([1,sum(2,2),sum([2, sum([sum_list(3), sum_list(3), sum_list(3)]), 2])])

-->sum([1,4,sum([2,sum(3,3,3),2])])

-->sum([1,4,sum([2,9,2])])

-->sum([1,4,13])

-->18

Once you complete other such examples, some steps that I did in this example can be omitted because you would know that you have already performed in the steps thus no need to write it again. Who likes to do the same thing over and over again? Where is the fun in that right? If I by any chance lost you in the example, do not panic and do what I did. PRACTICE, PRACTICE AND PRACTICE.

For me I find that it becomes a bit easier to trace a recursive code, once you understand the function of the base case because other cases generally repeat the action of the base case. In the above example the base case is the instance where you begin with an L that is a non-list, what do you do then? You simply return the value of L. Then you would trace another simple case where you begin with L that is a list but only contains 1 item. Then the function simply perform sum_list on that 1 item and returns it. Then you would move on to something that we traced earlier sum_list([4, 1, 8]) where you simply perform the function sum_list on each of the item but if the statement requires you to further complete an additional step, which is to return the sum of list.  My classmate Andrew also finds it helpful to understand the base case to be able to trace recursive code efficiently.  In the lab this week, we traced more recursive codes, which was extremely beneficial in sharpening my tracing skills. I can now confidently say that I would be able to tackle a recursive code based on my practice. My classmates impressions on recursion are somewhat divided.  Nicole in her blog shares similar experience as mine because she also feels tracing recursion to be simple if one were to understand the general case then slowly move on. 

I shall take your leave now and write to you soon hopefully regarding more interesting concepts to come in CSC148. Till then everyone. Be sure to share your experience with recursion and how you overcame your difficulties if you had any.