Basics: Recursion and Induction

Time for another sort-of advanced basic. I used some recursive definitions in my explanation
of natural numbers and integers. Recursion is a very fundamental concept, but one which many people have a very hard time wrapping their head around. So it's worth taking the time to look at it, and see what it means and how it works.

The cleverest definition that I've seen of recursion comes from the Hackers dictionary. In there, it has:

recursion
    n. See {recursion}.

Recursion is about defining things in terms of themselves. For what is probably the canonical example, think about the factorial function. For any positive integer N, the factorial of N (written N!) is the product of all of the integers less than it:

• 1! = 1
• 2! = 1 × 2 = 2
• 3! = 1 × 2 × 3 = 6
• 4! = 1 × 2 × 3 × 4 = 24
• 5! = 1 × 2 × 3 × 4 × 5 = 120
• ...

But if you look at it, you'll see that that's a cumbersome way of saying it - because there's a pattern. Written out as they are above, you can see that each number's factorial includes the factorial of all of the numbers before it - 2! is "1 × 2"; "3! = 1 × 2 × 3" - so 3! is the same as 2! × 3. And it works that way for every number: for any number N greater than 1,
N! = (N-1)! × N. Now, let's use that fact to make the list simpler:

• 1! = 1
• 2! = 1 × 2 = 2
• 3! = 2 × 3 = 6
• 4! = 6 × 4 = 24
• 5! = 24 × 5 = 120
• ...
• N! = (N-1)! × N

So that's the first piece of recursion: a definition in terms of itself: the definition of the factorial of a number N is defined in terms of the factorial of some other number.

So can we say that in general, N! = (N-1)! × N?

Not quite. Let's take a look at why. Let's pretend that we could use that, and try to compute 3!: 3! = 3 × 2! = 3 × 2 × 1! = 3 × 2 × 1 × 0! = 3 × 2 × 1 × 0 &times -1! ... = 0.

We've run into two problems. One of them is that as a procedure, it never finishes. There's always another N-1 - you can always subtract 1 from any number - and since we said that for any number, N! = (N-1)!×N, that means that we need to keep going forever. The second is that for any positive number, it will always give the answer 0 - because any string of multiplications containing zero will always end up returning 0, and repeatedly subtracting one from any positive number will eventually get to zero.

To make recursion work, you need something more than just a definition in terms of itself. A definition in terms of itself with nothing more is just a circle; you need something base to start from, some point, so that instead of being an endless circle,
it eventually reaches an end. That starting point is called a base case.

For the factorial, the way that computer scientists like me do that is say that the factorial of 0 is 1 by definition. Zero is the base case, and the value of the factorial is defined non-recursively for the base case. So then our definition of factorial consists of two clauses: the base case, and the recursive case:

• Base case: 0! = 1
• Recursive case: ∀ N > 0, N! = (N-1)! × N.

With this definition, things work as they should. factorial is only supposed to work for positive numbers; and for any positive number, the recursive definition will expand until it hits 0!, and then it will stop. So let's look at 3! again:

3! = 2! × 3 = 1! × 2 × 3 = 0! × 1 × 2 × 3 = 1 × 1 × 2 × 3 = 6.

Recursion is often used in math in another way: often, one of the easiest ways to prove something is called induction; induction is nothing but using recursion to define a proof.

For a very typical example, we can look at something similar to the factorial. What
if, for some natural number N, we want to take the sum of every number from 1 to N? We'll write that as S(N). We can write a simple recursive definition of S(N):

• S(0)=0
• For all N > 0, S(N) = S(N-1)+N.

It happens that there's also a non-recursive equation for it: the sum of all of the integers from 1 to N = S_N = N×(N+1)/2. Here's how we can prove that.

We start with a base case. We only need one, but just for the exercise, let's work
through two examples.

• By the recursive definition, S(1) = S(0) + 1 = 0 + 1 = 1.
  By the equation, S(1) = 1 × (1+1)/2 = 1×2/2 = 1.
• By the recursive definition, S(4) = 0 + 1 + 2 + 3 + 4 = 10. By the equation,
  S(4) = 4×(4+1)/2 = 4×5/2 = 20/2 = 10

Now we look at the inductive case. We assume that the equation is true for a value N, and we prove that if it's true for N, then it will also be true for N+1. So, we assume that S(N) = N×(N+1)/2; and we want to prove that S(N+1) = (N+1)×(N+2)/2.

1. We know that S(N+1) = (N+1) + S(N).
2. We know S(N) by our assumption. So S(N+1) = (N+1) + (N×(N+1)/2)
3. Now, we do a bit of algebra to expand out and simplify: S(N+1) = (N+1) + (N²+N)/2.
4. We can multiply (N+1) by 2/2 to give it a common denominator, and then add
   the two terms together: 2(N+1)/2 + (N² + N)/2 = (N² + 2N +2)/2.
5. And finally, we can factor: S(N) = (N² + 2N +2)/2 = (N+1)×(N+2)/2.

So, we've shown that for the base case of 1, the equation holds. By induction, if it's true for 1, it's true for 2. If it's true for 2, it's true for three. And so on... So it holds for all of the natural numbers.