Week 7 - Recursion

Recursion is a confusing little thing but once you know how to use it its kind of beautiful. Here I will highlight a few of my favourite examples.

The first is simple. A function called 'sum_list' might say this:

return sum([sum_list(x) if isinstance(x, list) else x for x in L]) where L is the list or object.

When I first looked at this, I was perpetually confused and thought it was the stupidest thing on earth. The way I read it in my mind, was "if x is a list then return the sum of the sum_list" which made absolutely no sense at first because wasn't sum_list what we were trying to write in the first place? How was this function going to take the sum_list of something if sum_list was the function being created?
After some time I came to realize that the essential part of this function lies in the else statement. If x is a list, then sum_list will repeat itself, but now the items in the list are being looked at individually. So if the items inside the list isn't a list, sum_list will only look at the item and will add it to the sum. It's wonderful.

Another example of recursion is as follows (excuse the poor stylistic elements):
def remove3s(L: list):
I = 0
while I < len(L):
   if isinstance(L[I], int):
      if L[I] == 3:
         del L[I]
         continue
elif isinstance(L[I], list):
         remove3s(L[I])
I = I + 1

This function strives to remove all 3s from a list L. It takes into consideration the possibility that L[I] might be another nested list, so it calls itself if that's the case. When it calls itself, it takes the nested list as the new L and goes through each element in the nested list.

Recursion is also useful in the class Tree:
def leaf_count:
if len(t.children) == 0:
   return 1
else:
   return sum(leaf.count(c) for c in t.children)

Something is a leaf of a Tree if it has no children. In Trees, though, it's not just as simple as there being parents and children, because children can have children who can have more children. In this case, because Trees multiply in such a repetitive way, and each Tree contains more Trees, recursion is necessary. This method says that if a tree has no children, return 1 because this means there is one leaf. However, if a tree does have children, these children might be leaves themselves so the function has to go back and also see if the children have any children.

And that pretty much sums up my little blurb on recursion!