Clarifying Recursion

I managed to confuse a lot of people yesterday in my post on building math, because I forgot that normal people don't understand recursion. For a computer scientist, or a mathematician involved in logic, recursion is so fundamental that it's easy to forget that when you first see it, it looks like some kind of bizzare magic. In my day job, where I'm currently doing software development, I use recursion every day.

Hopefully I can clear up that confusion.

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

Recursion

see "Recursion"

Recursion is about defining things in terms of themselves. For example, think about the factorial. 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 that's a cumbersome way of saying it. Instead, if you look at it, you can seee that there's a pattern: the factorial of each number N is the product of a sequence of numbers, and that sequence is exactly the same as the sequence for the number before it, with N added onto the end.

Let's use that fact to make the list a bit simpler; let's just replace the sequence for everything but N with the product of the numbers in that part of the sequence:

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

Now the pattern should be reasonably easy to see: look at 4! and 5!; 4! = 24; 5! = 5 * 24. Since 4! is 24, we can then say that 5! = 5 * 4!.

So we can say that in general, N! = N * (N-1)!.

Except that that doesn't quite work. Let's take a look at why. Let's use that to compute 3!: 3! = 3 * 2! = 3 * 2 * 1! = 3 * 2 * 1 * 0! = 3 * 2 * 1 * 0 * -1! = ...

To make recursion work, you need to define a base case: that is, you need to define a starting point. For factorial, the way we do that is say that the factorial of 0 = 1. Then things work: 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! = 3 * 2! = 3 * 2 * 1! = 3 * 2 * 1 * 0! = 3 * 2 * 1 * 1 = 6.

The way that we write a recursive definition is to state the two cases using conditions, in something that looks almost like a little bit of a program:

• N! = 1 if N = 0
  
• N! = N * (N-1)! if N > 0
  

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 recursion. What if we want to take the sum of every number from 1 to N? Let's write that as S_N. Well, there's an 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. Let's do two of them, just for the heck of it:
  
  
  
  • if N = 1, then the sum of all integers from 1 to 1 = 1. According to the equation, that's 1(1+1)/2 = 2/2 = 1.
    
  • if N = 2, then it's the sum of all integers from 1 to 2 = 1 + 2 = 3. According to the equation, that's 2(2+1)/2 = 2*3/2 = 3.
    
  
  
  
• 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.
  
  
  
  
  • Assume that S_N = N*(N+1)/2
    
  • We want to prove that S_(N+1) = (N+1)(N+2)/2.
    
  • We know that S_(N+1) = (N+1) + S_N
    
  • We can expand that to: (N+1) + N(N+1)/2
    
  • We can expand further: (N+1) + (N^2 + N)/2
    
  • We can multiply (N+1) by (2/2) so that we can combine things; since 2/2=1, that doesn't change anything: (2N+2)/2 + (N^2 + N)/2
    
  • Now we can add the numerators: (N^2 + 3N + 2)/2
    
  • Now we factor the top: (N+1)(N+2)/2.
    
  
  
  
• So, we've shown that for 1 and 2, the equation holds. Since it holds for two, by the induction it holds for 3. If it holds for 3, by the induction, it holds for 4, and so on.
  

If you followed this, congratulations, you understand recursion! If you didn't, please ask questions in the comments, so that I can try to fix this until it's comprehensible.