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:

recursionn. 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 × -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.

- We know that S(N+1) = (N+1) + S(N).
- We know S(N) by our assumption. So S(N+1) = (N+1) + (N×(N+1)/2)
- Now, we do a bit of algebra to expand out and simplify: S(N+1) = (N+1) + (N
^{2}+N)/2. - 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^{2}+ N)/2 = (N^{2}+ 2N +2)/2. - And finally, we can factor: S(N) = (N
^{2}+ 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.

Anthony MillsSaying it this way always helped me: recursion is about defining things in terms of

simpler versionsof themselves. And usually at some level the simpler version is defined outright.Craig StuntzGood post, but I think you have a typo on line 5 of the proof. It says:

I think that should read “S(N+1) = […]”

Thanks for doing these; it’s good to think about the basics!

Torbjörn LarssonWe have also, paradoxically times twice:

induction

n. A certain proof method based on {deduction}. (math)

n. Inducing the universal from the particular. (philosophy)

Torbjörn LarssonFrak! Hopefully this brings out the paradox and humor:

induction

n. A certain proof method based on {deduction}. (math)

n. Inducing the universal from the particular, a method not based on {deduction}. (philosophy)

brianbecI really enjoy the clarity of your walkthroughs. Can I entice you into cooking up a nice example of co-induction (as opposed to mere induction)?

OxeadorI thought you would like to know that recursion is taught at Sesame Street.

Øyvind StenhaugThere’s another typo/mistake in steps 4 and 5, it says

instead of (N2 + 3N + 2)/2.

Jesse Merriman<pedantic>

Unless that string contains infinity, which would make the result of the multiplication undefined.

</pedantic>