CSC148 Recursion Post #3

In Week 4, we talked about recursion. Basically recursion is calling a function in itself. So in class we were given a worksheet and we had to trace a recursive function. Getting a worksheet again reminds me of CSC108 where we got a worksheet for the lesson and we were able to go through the worksheet with the professor. To be quite honest, I think getting worksheets in class help me more than just watching Professor Heap code. It allows me to think about what we are doing and actually try it myself. It would be best if Professor Heap could hand out worksheets for the lesson and we could go through it.

Anyways back to recursion, on the worksheet, the given recursive function was:

def sum_list(L):
     if isinstance(L, list):
          return sum([sum_list(x) for x in L])
     else:
          return L

This function takes in a list as an argument and essentially checks if the argument is a list, if it is not a list, then the function will return the argument. If it is, then it will return the sum of the list where for each item, the function calls itself again to see whether or not the item in the list is a list. Now this is the recursive part, the function is calling itself within itself to check whether or not the item is a list.

To make sense of what's going on here, this an example from our worksheet:

sum_list([4, 1, 8])

In this example, the argument that is passed in is a list, which means it satisfies the first if condition. Now the function will proceed to return the sum of the elements in the list, where for each element, the function will call itself again to check whether or not the element is a list. So for 4, the function will pass in 4 for L and check, since it is not a list, the function will simply return 4 back into the list comprehension. It will do the same for 1 and 8 as well, so at the end of the recursive checking, the final list that will be summed is [4, 1, 8]. Thus the final result is 13.

Now if in the original list, one of the elements was a list, so in other words a nested list was passed in as the argument, then the function will call itself, while it has already called itself. So in this case, we would have gotten into depth 2. The more nested lists there are, the more depths we go into.

So this is recursion and my understanding of it. I think recursion is actually pretty simple once you get the hang of it, though I don't see any practical use for recursion yet. I hope that we will see some functions that will make use of recursion in a useful way, instead of just seeing simple functions that just calculate.

Thanks for reading!