We must go deeper!

Recursion seems to be a very big theme in this course, and also one of the things that people seem to have the most trouble dealing with. So what is it?

Well there are 2 (kind of similar) answers, one is how I and many others think of it, and one is the official understanding of what it is.

First the official version, mainly so we can forget about it and move on immediately after. According to Miriam Webster, recursion is:

The determination of a succession of elements (as numbers of functions) by operation on one or more preceding elements according to a rule or formula involving a finite number of steps.

Huh?

Well, let's look at some examples and come to an understanding of what it is ourselves.

The first example I was exposed to, waaaaaaaaay before starting this course is my old friend the factorial. In math, a factorial is essentially a number multiplied by all the successive numbers between itself and 1. For example: 7! = 7x6x5x4x3x2x1, 4! = 4x3x2x1 etc. Factorials are incredibly useful in probability since they represent the amount of ways you can arrange a group of objects.

So how would this look in python?

Well, one way is like this:

def factorial(n):
      total = n
      for num in range(1,n):
            total *= num
      return total

Which certainly works (and one might argue would be a little easier on the ol' computer memory) but we can write a "simpler" *cough* version using recursion. Here's how it would look:

def factorial(n):
      if n == 1:
            return 1
      else:
            return n*factorial(n-1)

So here is the big breakthrough here, we can write functions that call THEMSELVES, which is what recursion is. Factorial is perhaps a bad example, because you might be asking me "Well, why would we bother hurting our brain trying to write that when I can just write the other version that is easier for me to understand?" To which I would reply "so you can be lazy later".

Here is what I mean.

Let's say we have a list of numbers and we want to sort them, and we want to sort them as fast as we possibly can (not exactly but we can pretend for sake of example). We want to use a magical type of sorting called quick sort! But what is quick sort?

Imagine we have a list of items: [1,6,3,4,2,5] and we want to sort them fast, first we will choose a random number called a "pivot", in this case we will choose 3. Then what we do is we make 2 more lists, one that has numbers less than 3, and one that has numbers greater than 3, which in this case would yield:

pivot = [3]
less = [1,2]
more = [6,4,5]

Then we do the same thing to less, and more. So for less we might choose 1 as the pivot, so only 2 gets put into more and nothing gets put into less, and for more if we choose 5, 4 gets put into less etc. Then when it is all done we put it together, so we would have something like:

less' less = []
less' pivot = [1]
less' more = [2]

Added up becomes [1,2] and:

more's less = [4]
more's pivot = [5]
more's more = [6]

Added up becomes [4,5,6]

So then we have, originally:

less = [1,2]
pivot = [3]
more = [4,5,6]

And added up is [1,2,3,4,5,6], our sorted list!

Written in non-recursive code this is a bit of a nightmare, as you would have to have a bunch of variables to account for all possible permutations of the six items so that we can quick sort them with a bunch of nested if and else statements. Then if we passed a list with 7 items, suddenly it wouldn't work consistently anymore, and we would have to add more nested if and else statements.

Talk about a lot of work! Luckily for us we can be lazy bums and write this recursively and save ourselves the time. Here's how that would look.

def quicksort(list):
      if len(list) <= 1:
            return list
      else:
            pivot = [list[0]]
            more = []

            less = []
            for number in list[1:]:
                  if number >= pivot[0]:
                        more.append(number)
                  else:
                        less.append(number)
            return quicksort(less) + pivot + quicksort(more)

Which is actually pretty simple! All it requires is calling our function for the smaller lists until we end up with a list of one/no items, which is already sorted for us :-).