Week 5: Recursion is recursion is recursion

....is recursion. Need I say more?

Last week, we constructed our knowledge on recursion. We looked at tracing recursion on nested lists. I found it to be like simple math.

How does this work? Well, let's say we have a list. Consider this list: [3, 5, 7, 9]. Now, we want to trace recursion on this list of ours. It's a list of four elements consisting of type int.

We can trace recursion in many different ways. One example that Professor Heap showed us in class is the sum_list function, which returns the sum of the elements if a list, L, or 1 if it's not a list. Here's what the function looks like in Python (complete with docstrings and all). I'll trace sum_list on our given list.

def sum_list(L):
    """ (list or int) -> int

    Return L if it's an int, or sum of the numbers in a possibly             nested list.
    
    >>> sum_list(34)
    34
    >>> sum_list([2, 7, 1])
    10
    >>> sum_list([2, 6, [3, 8, [5, 3]], 3)
    30
    """
    if isinstance(L, list): # isinstance checks whether L is list
       return sum([sum_list(x) for x in L)
    else: # L is an int
       return L

Going back to our list, [3, 5, 7, 9], we can trace it like so:

sum_list([3, 5, 7, 9]) --> sum([sum_list(x) for x in [3, 5, 7, 9]])
--> sum([sum_list(3), sum_list(5), sum_list(7), sum_list(9)])
--> sum([3, 5, 7, 9])
--> 24

Ta-da! We got the sum of all the elements in our list, which is 24. (Let's celebrate by drinking some hot chocolate.)

An even simpler call is on an int, say, 56. (You can even do this with crazy large numbers, like 243432423532523.) We'll just get 56 back because it's an int. But we can still trace this call (although it's literally just one line) like we did to the list above and add some comments:

sum_list(56) --> 56
# 56 is not a list
# as stated in our docstring, return 56

I had my test on Wednesday morning. It was only three questions. It wasn't terribly hard. (My MAT137 test was, though.) I'm hoping it went well. (Fingers crossed. I won't fret if I get a low mark, unlike what I did in CSC165 last semester. Haha! That is funny now.) The lab exercise on recursion wasn't as hard as the first two labs, either. The quiz followed suit. 

I'll also be adding blogs on my blogroll to your right, so you can read other people's SLOGs that I have garnered inspiration from.

Thank you for reading! Until next time!