Week 7: Recursion

Recursion is a programming methodology that at first may be difficult to wrap your head around, as it was for me, but once understood, the possibilities are endless! (well sort of)...

Recursion, but why?

What does a recursive function do? and why is it useful?

At its core, a recursive function is a function that calls itself, and continues to do so until a condition is met.  It breaks down a difficult task, into smaller, more manageable subtasks, until the final task is trivial and the problem is solved. The lure of a recursive function is in its simplicity and power. A couple of lines of code can do a lot of heavy lifting.

To truly appreciate the awesome power of recursion, lets consider a list that is composed of arbitrarily nested child lists, much like the following:

[ ‘a’, ‘b’, [ ‘c’, [ ‘d’ ], [ ‘e’, [ ‘f’, ‘g’ ] ] ] ]

If you were tasked to write a “list counter” program that counts every instance of a list within the list above, how would you go about doing it?

The inclination would be to write the program as a series of nested loops. You’d want to traverse each child node in the list, check if it’s an instance of a list type, go onto the next child, check if itself has children, all the while keeping track of the length of a child list, adjusting the iteration and counter accordingly. Implementing an algorithm of this type is, as I’ve discovered, quite difficult.

The makings of a recursive function

There isn’t anything inherently wrong with the “list counter” algorithm as described above. Theoretically, if we could code it, it would do the job. To make our life easier though, we could attempt to “recursify” this algorithm. Before we can do that, we need to know what makes a recursive function so darn recursive and why it would work in this particular case.

A recursive function must satisfy the following principles:

1. Has a basecase

2. Moves towards the basecase

3. Calls itself recursively

The basecase of a recursive function is its “escape route” and it should always have one in mind. A recursive function should end at some point and it ends when it reaches its “escape route”, its basecase.

It may be a long and tiring journey to the basecase but it should always be moving towards it.

Finally, the function should, at every stage of the journey towards the basecase, call itself.

So why would recursion work so well in our case? Because we can simplify the problem down to a few important tasks that are repeated over and over until a certain condition is met.

The tasks are:

1. Checking whether an object is of type list

2. Incrementing the counter if an object is a list

Those 2 tasks are the basis of our recursive function.

Putting recursion to use for “list counter”

Lets put these recursive principles into action and code ourselves a “list counter”, shall we?

def list_counter(lst, count=0): # We give the count a default value of 0

  

   # Loop through each item in lst

   for item in lst:

       

       #Basecase: Is item of type list ?

       if isinstance(item, list):

           

           # Recursive self call: If item is a list,

           # then call list_counter  with nested list

           # and incremented count as arguments           

     count = list_counter(item, count + 1)

   

   # return value of count for each stage

   # of recursion when basecase is reached

   return count

We can get a better sense of the recursive nature of list_counter() by referring back to the 3 recursive principles we were introduced to.

1. Has a basecase

Indeed list_counter() does! The basecase being, a lack of objects that are of type list. The only way this recursive function will end is by no longer encountering nested list objects at each level of recursion.   

2. Moves towards the basecase

Everytime list_counter() encounters a nested list and then dives into that list by making a recursive call to itself, it is getting closer and closer to a point where there will no longer be a nested list, that point being its basecase.

3. Calls itself recursively

When list_counter() encounters a nested list, it calls itself, and passes itself the newly discovered nested list and an incremented instance of the variable count.