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.

Week 6: A world of objects

Our discussion of Object Orient Programming in week 6 has a close connection to the 4th week discussion on Abstract Data Types. In a way, this post continues from where we left off in week 4.

As previously discussed, an Abstract Data Type describes a solution to some programmatic problem. When an ADT is implemented it becomes a class and instances of this class are called objects. With that, we have our foray into Object Orient Programming!

Object state and behaviour

Objects in computer science often correspond to things found in the real world. One such object could be a car, telephone or even a dog! It could literally be any object that a program needs to handle. What I find most appealing about Objects in the programming world, is that they are self-contained modules that bind methods to the data they contain. Put simply, objects are neatly organized packages of methods and data that can be easily used over and over again.

Most (if not all) objects contain some data during their lifetime. This data describes their state at any given point. An objects data does change, It’s added, removed and updated by functions that are specifically designed for this object. We can get a sense of what an object is meant to do by reviewing these functions and so we get an impression of it’s behaviour.

Object hierarchies and inheritance

Another interesting thing about objects is that they exist within a hierarchy. The top most object in a hierarchy can pass down some or all of it’s properties (data and functions) to lower objects through inheritance. If a change is required at the bottom of the hierarchy, it is possible to make the change without worrying about the consequences this may have on other objects that are further up the chain.

Week 5: Tracing a recursive function

Like with many other things, it takes time and practice to master recursion. Thankfully we have a technique at our disposal which makes learning recursion easier. This technique is referred to as “recursive tracing”.

Tracing a call to a recursive function is a great way to understand how the recursive function behaves, and inevitably when errors crop up, it’s also a good way to troubleshoot and fix bugs.

Winding and unwinding recursion

When tracing most recursive functions, there are 2 phases that occur one after the other.

First we have the winding phase, which occurs at every level of recursion. It occurs every time subsequent calls to a recursive function (usually the same function) are made. The winding phase will continue until it reaches a dead end, a point which is referred to as the “base case”. The base case is a condition in which further recursive calls are not necessary.

The unwinding phase occurs when the base case condition has been satisfied. It is at this point the recursive process travels back up the recursive levels and returns some final value.

Winding and unwinding is not something native to only recursive functions. We’ve seen this occur with many ordinary functions. Suppose that a function a() makes a call to function b(), which inturn makes a call to function c(). Once function c() has done it’s job, what happens next? It goes back to b() and then a(). So we can think of going from a() → b() → c() as the winding and back from c() → b() → a() as the unwinding.

How to trace a recursive function

Let’s say that we wanted to implement a recursive function called check_for_occurance that checks for the occurrence of some object within a list and returns a boolean value. Object and list are arguments of our function.

Here’s the code for our function:

def check_for_occurance(obj, lst):

   '''(Obj, list) -> Bool

   

   Return True if obj exists in lst (the 1st occurrence of obj), otherwise return False.

   

   >>> check_for_occurance(1, [0])

   False

   >>> check_for_occurance(1, [0, [1]])

   True

   '''

   

   index = 0

   

   # Base case: Is obj in lst?

   found_obj = obj in lst

   

   while not found_obj and index < len(lst):

       

       # General case: Iterate through lst and recurse on item that is itself a list

       if isinstance(lst[index], list):

           found_obj = check_for_occurance(obj, lst[index])

       index += 1

       

   return found_obj

Note: In our implementation we rely on the python ‘in’ operator to do a check for an item in a list. However, it does so only on the first level of a parent list. It ignores nested child lists.

To understand how check_for_instance works, we begin by tracing a simple example and then work our way up to a more complex example.

Simple tracing example

check_for_occurance(1, [0]) → False

In the simple example we see that the list has only one level and therefore does not require any recursive calls. Also, we can see that the integer 1 is not in the list so the function returns False.

Slightly more complicated tracing example

check_for_occurance(1, [0, [1]]) → check_for_occurance(1, [1]) → True

In the slightly more complicated example, the list has two levels. The first level does not contain a 1, but it does contain another child list (the second level) so we need to make a recursive call on the child list. Lo and behold the child list does contain a 1 so we expect to have True returned.

So to conclude then, by tracing out the recursive calls to check_for_occurance we’re able to see what is happening at each of level of it’s recursion and what the return value should be.

Week 4: Abstracting away complexities

When we think of the term “abstract”, perhaps the first thought that comes to mind is abstract art. Abstract art holds little or no resemblance to real world objects. The use of lines, shapes and colours in abstract art is typically no where near accurate. This is why someone looking at abstract art may stare at it for hours without understanding what the piece is meant to represent.

We see this word “abstract” in computer science, but unlike it’s artistic variant, abstraction in computer science aims to simplify and consolidate our understanding of complicated programmatic operations without needing to write a single line of code.

Abstraction in action

To put abstraction to use, we’ll begin with a problem, one that was discussed in lecture and one whose solution was first proposed back in 1946 by Alan Turing.

Problem: Given some items (objects/values etc.), we’d like to build a collection of these in ascending order, and be able to add to the collection, and return the latest item when necessary.

Before we jump the gun and think about the code that could solve the problem, we first need to describe the solution so that we’re able to define a model.

Solution: The Stack model. A Stack contains various types of items. New items are pushed (added) onto the top of the Stack, the latest (or top most) items are popped (retrieved) from the top of the Stack. It’s not possible to pop an item from an empty Stack.

Our solution is fairly basic but it has two important properties which are common to all Abstract Models/Abstract Data Types:

• describes a solution which could be implemented in any programming language
• describes the data it contains and the actions that can be performed on the data

The Stack Abstract Data Type exists independent of any implementation. Abstract Data Types serve as blueprints or recipes so that they may be easily understood and implemented in any given programming language. However, it’s not guaranteed that all implementations of the ADT will work the same. Some implementations may perform more efficiently than others.

Our Stack solution makes references to nouns, such as item and verbs such as pushed and popped. When describing an ADT, nouns become the data and verbs become the actions (or methods) performed on the data. Select nouns and verbs define the underlying structure of an ADT.

So where do we go from here? We’ve defined our Stack ADT, the next step would be to implement it in our favourite language. Once implemented, the ADT takes on the role of a class, which is a topic for another post.