Week 7: Recursion

Let's start with what recursion is...

Recursion is a method of solving a problem that is made up of smaller problems that are all of the same format as the big problem.

At first glance, this seems both confusing and somewhat useless. How am I supposed to solve a problem that is made up of essentially itself? For me, the key part to understanding recursion was the idea of having a base case and a recursive case. The base case is simple and easily solved and the recursive case is made up of the smaller problems that look like the main problem. So the idea is that all the recursive cases will eventually boil down to the base case (which we can solve) and then we can solve the main problem.

The structure of a (very basic) recursively defined function can look something like this:

       def big_problem(n):
           """ Solve this problem recursively. """
      
           # Base case
           if n == 0:
                  do something
           # Recursive case
           elif n != 0:
                  do big_problem(n-1)


Now if we think about this, for smaller recursive cases (i.e. 'n' is small) we can trace by hand what to do and eventually get down to a solution in terms of the base case which we can solve. But what if 'n' is very large or the body of the recursive case is more complicated than the function above? These are situations where recursion shows its true value. It can take a complicated solution to a problem and turn it into a very simple solution to code, provided of course, you can identify when to use it. And the easiest way to do this is by checking the definition given at the start.

So it's two thumbs up for recursion from me, adieu!