Recursion

Recursion is actually a pretty simple concept, but people sometimes have trouble implementing it.

You know what the factorial operation does in math? It takes a number (say, five) and multiplies it by every smaller number, down to one. For example:

5! = 5 × 4 × 3 × 2 × 1 = 120

See how easy that is? So easy. There are many different ways to teach a computer to do that, but the most common is to use recursion.

Now it’s time to define recursion: a recursive function is a function which uses itself in its own definition.

“Wait a minute,” you might exclaim, “my English teacher told me that we couldn’t use a word in its own definition because people wouldn’t understand it. Wouldn’t computers, being nothing but logic, have an even harder time with that?” Excellent question. Maybe we should define recursive functions twice, once without using the function in its own definition.

So, let’s look at some examples of factorials.

1! = 1
2! = 2 × 1! = 2 × 1
3! = 3 × 2! = 3 × 2 × 1
4! = 4 × 3! = 4 × 3 × 2 × 1

Any ideas for how to write that algorithmically? How about:

factorial(1) = 1
factorial(n > 1) = n × factorial(n − 1)

And there you have it: something that uses itself in its own definition, but still won’t confuse a computer. Take that, imaginary English teacher!