We keep hearing about “Global complexity through local interaction” as being one of the keys to solving highly complex problems with simple code and functions. This section will pull together many of the lessons learnt throughout the course, but first, let’s take do a gentle introduction to recursion. Simply put, it is a way of solving a problem with a function that calls itself. For example, how do we calculate the value of a factorial?
- 2! = 2 * 1
- 3! = 3 * 2 * 1
- 4! = 4 * 3 * 2 * 1
- 5! = 5 * 4 * 3 * 2 * 1
There’s a clear pattern here, as to calculate a higher factorial number, let’s say n, we multiply n by the factorial the number less than it, giving us:
Factorial n = n * Factorial (n-1)
Although, not exactly, as this will never stop, and the value for n will just keep getting smaller and smaller.
Before we fix that, let’s do a quick reminder of Induction, which is a way of proving properties for numbers. Induction works by first proving something for a simple case, then for case i+1, that is, a general case, and then assuming the property is true for all numbers.
Imagine we’re trying to prove that a row of dominoes will all fall if the first gets pushed over. Informally, we could say:
- The first domino falls
- The first domino knocks over the second
- Which knocks over the third
- … and so on
To put that in more formal terms, we could say:
- The first domino falls
- When domino i falls, it knocks over domino i+1
- There, all dominoes fall
And this is reasonable enough, as we know that, in general, if a domino falls, it will knock over the next one. This is important because numbers go on to infinity, so we can’t prove properties for every single one, but if we can generalise, we can prove something. In particular, this is important to us as Computer Scientists because if our applications are large enough, we can’t test them on every possible input case, but we still need to be sure that they will work on all cases.
Recursion works in a very similar way. We first figure out how to solve the simplest case of a problem, and then figure out how to solve a general version of the problem, using the simple case. Then, somehow, when we put them together, we can solve every possible case. Consider the factorial example. The simple case is Factorial 1, which is 1. We know from earlier that the general case is:
- Factorial n = n * Factorial (n-1).
What happens if we try to run through this? Let’s calculate the value of Factorial 3:
- Factorial 3 = 3 * Factorial 2
But what is Factorial 2?
- Factorial 2 = 2 * Factorial 1
Okay, so what is Factorial 1?
- Factorial 1 = 1
We finally have answer, so now we work our way back up, filling in this answer:
- Factorial 2 = 2 * 1
And fill this in for Factorial 2:
- Factorial 3 = 3 * 2 * 1
That gives 3 * 2 * 1, which is nice and easy, so our answer is 6. Each line does exactly one thing: it easier makes the problem slightly easier by bringing us closer to the simple case or it helps reassemble a more complex case.
Next up, let’s see how we could use this in a program.