Revisiting My Post About Recursion

    My third blog post was about recursion. You can tell I was not prepared to write about recursion at the time since I had to Google it in the first place. Here's the post:

http://sloglogblogslog.blogspot.ca/2015/02/week-4-recursion.html

    Now that I have been working with recursion for longer, I can safely say that thinking about it only makes my brain sore rather than the searing pain it used to cause. So, let's get a little more in depth, and walk through the process of writing a recursive function, and explain why it works.

    Let's say we want to write a function that takes a nested list of integers, which could be lists within lists within lists but ultimately they contain integers, and sums them all up. The first thing we want to do when writing a recursive function is decide what the function should do if no recursion is required. In this case, a single integer would be the simplest input, in which case we should simply return the integer. But we should only do this if the input is an integer, so we get:

def recursive(m):
    if type(m) == int:
        return m

    Now we need to know what to do when we are given a list. This would be as simple as summing up the values in the list, which we can do with a default python function.

def recursive(m):
    if type(m) == int:
        return m
    else:
        return sum(m)

    Unfortunately this will only work for integers and flat lists. Let's see what we would write for a list of lists.

    def recursive(m):
    if type(m) == int:
        return m
    else:
        return sum([sum(x) for x in m])

    Now for a list of list of lists...

    def recursive(m):
    if type(m) == int:
        return m
    else:
        return sum([sum([sum(y) for y in x]) for x in m])

    You can see that this isn't very good, as the expression will just keep getting longer and longer, and will only work for exactly the right kind of list. This is where recursion saves the day.

    def recursive(m):
    if type() == int:
        return m
    else:
        return sum([recursive(x) for x in m])

    This seems almost too good to be true. How is there such little code? How is this even supposed to do what we expect it to? Well, let's trace an example.

>>> m = [2, 4, [2, 6], [[4]]]
>>> recursive(m)
    -> sum([recursive(2), recursive(4), recursive([2, 6]), 
           recursive([[4]])])

    We already know that recursive(2) and recursive(4) will return their inputs, so lets keep breaking down what this function is doing.

    -> sum([2, 4, sum([recursive(2), recursive(6)]),
           sum([recursive([4])])])
    -> sum([2, 4, 8, 4]) -> 18

    As can be seen, recursion is witchcraft and is only practiced by those wicked of heart.