Recursion is when code calls itself.
In my first programming class, everyone thought recursion was hard. It’s hard for many of us to get our heads around at first. But we get used to it with a little practice.
The classic first recursive function is the factorial function.
(The factorial of a number n is the product of all positive integers less than or equal to n. The factorial of 0 is 1. The factorial of 1 is 1. The factorial of 2 is 2 * 1. The factorial of 3 is 3 * 2 * 1. The factorial of 4 is 4 * 3 * 2 * 1. And so on.)
Here’s an implementation of the factorial function in Javascript:
function factorial(n) {
if (n === 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
A recursive function needs to avoid calling itself infinitely. It needs what’s called a “base case”, in which it does not call itself.
If I call factorial(0), no recursion happens. The value 1 is returned. This is the function’s base case.
The cases where the function does call itself are called “recursive cases”.
If I call factorial(1), n * factorial(n - 1) is returned. Since n = 1, this evaluates to 1 * factorial(1 - 1). That’s 1 * factorial(0), or 1 * 1. The value 1 is returned.
When this first recursive case gets hit, it calls the base case. The base case returns its value, and the recursive case gets that result and uses it to return a value.
If I call factorial(2), n * factorial(n - 1) is returned. Since n = 2, this evaluates to 2 * factorial(2 - 1). That’s 2 * factorial(1), or 2 * 1. The value 2 is returned.
This recursive case with n=2 calls the recursive case with n=1, which calls the base case, n=0, which stops the recursion. The n=0 case evaluates, which allows the n=1 case to evaluate, which allows the n=2 case to evaluate.
And so on. The call stack gets deeper when the numbers get higher, but the evaluation pattern just continues like this.
When I learned about recursion, walking carefully through the calls and evaluations helped me to understand what was going on. So I recommend that, if you’re new to the idea. Just working a few examples like this can quickly make you much more comfortable with the concept.
(Another simple, common recursion example you might try working through is a function that computes the nth Fibonacci number.)
