I remember the first time I formally encountered recursion – it was sophomore year of high school and I was watching as my CS teacher, Mr. Kendall Chun, was explaining how instead of using loops, a function could repeatedly perform an action by calling itself. The concept at the time just completely blew me away. It seemed to me, like I think it does to a number of people when they first learn about it, almost magic. I used it on more of a faith basis until I became more comfortable with it – and now, like any programmer, it is a standard part of my arsenal.
What is Recursion?
While recursion is a powerful technique, there is definitely nothing mystic about it. Simply put, recursion is when a function uses itself in it’s own definition. It can be a little easier to demonstrate by showing an example.
Non-Recursive Function
First off, remember that a function is a dependence between two values – or in plain terms, it’s a “machine” where input goes into it, and output comes out. Usually that output is generated by doing something to the input.
Take f(x) = x+3. This is a simple function that says whatever I put in, I get that plus 3 out – so if I put 7 in, I get a 10 out. f(7) = 7+3 = 10. No biggie, the function is defined in terms of x – we put a 7 in for x, we got a 10 out – no recursion yet.
Recursive Function
The most classic example of a recursive function is the factorial function. For those unfamiliar, the factorial function multiplies all integers less than or equal to itself, and is represented by an exclamation mark. So 5!, or 5 factorial, is equal to 5 * 4 * 3 * 2 * 1, or 120.
Why is this recursive? Check it out:
- 5! = 5 * 4 * 3 * 2 * 1
- 4! = 4 * 3 * 2 * 1
- 3! = 3 * 2 * 1
- 2! = 2 * 1
- 1! = 1
So I’ve listed the factorials of each of these numbers out, so what? Well, if 4! = 4 * 3 * 2 * 1, then we could say:
- 5! = 5 * 4!
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
As can be seen, any factorial is the number going into it times the factorial of one less that number. This means that factorial uses itself as its definition -
f(x) = x * f(x-1)
Factorial is the number going into it (variable x) times the factorial of the number minus 1. So factorial of 5, or f(5), is 5 * f(4). What’s f(4)? 4 * f(3). f(3) = 3 * f(2), and f(2) = 2 * f(1).
The Base Case
The issue is that for recursion to be useful, it has to STOP somewhere. In the factorial example, nothing stops it. We would say f(1) = 1 * f(0), f(0) = 0 * f(-1), f(-1) = -1 * f(-2), ad infinitum. Endless loops are no fun (unless the basis of annoying pranks), so we need a way of saying STOP! This is where the “Base Case” comes in. It is simply a point during execution, or in the definition of the function, that says “no more calling yourself, stop the looping madness”.
In the case of factorial, it’s f(0). f(0) = 1. Period. It doesn’t involve itself any longer, it just returns 1 – it’s a static value, an axiom, a solid rock, where the buck stops. Every recursive function needs a base case.
Full Execution
So the full definition of our factorial function is
f(0) = 1
f(x) = x * f(x – 1)
That means, if we call f with 0, we get 1, otherwise we perform the second operation. Let’s try it out with 4. We should get 4 * 3 * 2 * 1 = 24.
- f(4) = 4 * f(3)
- f(3) = 3 * f(2)
- f(2) = 2 * f(1)
- f(1) = 1 * f(0)
- f(0) = 1
Now we know what each function returns, we can fill in the unknown values
- f(1) = 1 * f(0) = 1 * 1 = 1
- f(2) = 2 * f(1) = 2 * 1 = 2
- f(3) = 3 * f(2) = 3 * 2 = 6
- f(4) = 4 * f(3) = 4 * 6 = 24
It worked! And is very easy to implement in whatever programming language you happen to be using. Once you become comfortable using recursion, you’ll find it’s useful all over the place, because the world around us uses recursion constantly – it is a large part of math and our Universe.
Other Fun Examples
Looking for some more examples of recursion?
- The Fibonacci Numbers – 0, 1, 1, 2, 3, 5, 8, 13, 21, etc. Each number is defined by adding the two numbers before it – so f(x) = f(x-1) + f(x-2). Double recursion – it makes use of itself twice! Our base cases are f(0) = 0 and f(1) = 1.
- Any Geometric Series – The powers of 2 for example – 1, 2, 4, 8, 16, 32, 64, 128, 256. Each number is the previous number times 2. We could define this using exponents, but let’s do it with recursion! f(x) = 2 * f(x-1). Base case f(0) = 1.
Recursion rocks, so try finding some situations where loops are used that you could use recursion instead – it’s a lot more fun!
Articles and Posts