Recursion is a difficult concept. Even for seasoned software engineers, recursion is not an easy problem-solving method to wrap your mind around. Nevertheless, recursion is a powerful tool that illustrates precisely why we need computer programming: while it’s hard for the human mind to process a recursive function, this task is neither easier nor harder to a computer than a simple for loop; to the computer, it is simply executing code.
So what is recursion? The definition of a recursive function is “a function that calls itself.” I like to think of recursion as a function nested within itself, kind of like a two-layer Russian doll.
Let’s take a look at a sample recursive function that calculates the factorial of a number. That is, given a number n, we want to know the value of n! So if n= 5, the function below will tell us the value of 5!, which is 5*4*3*2*1 = 120.
function factorial( n ) {
if (n < 0){
return undefined;
} else if (n === 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}You see how the factorial function above calls itself? Within the function factorial is another factorial function, precisely like a two-layer nesting doll.
But what exactly is the factorial function above doing here? There are two things happening:
- There’s an if…else statement. This is something you often see in recursion, where the if statement executes the base case, and the else statement executes all other cases. What is a base case? A base case is when certain conditions are met and the recursive algorithm can finally stop calling itself and begin to return values. In this example, the base case is when n===1. Only when n is 1 do we get a return value of 1. In all other cases, the else statement gets executed, and the factorial function gets called again.
- OK. Now that we’ve gone over the if part, what exactly is happening within the else brackets? What does it mean that the function is calling itself? The best way to understand this is to find an example and try to work out the process the computer goes through, step by step. Let’s say we want to calculate 3! So the function takes n =3 and goes through the code line by line. Let’s try to think from the computer’s point of view for a while:
· Does n ===1? No, so go to else statement.· Return 3 * factorial (3-1). OK, we need to return
3 * factorial(2), but I don’t know what factorial(2) is. Luckily, the function has called itself, and we’re now going to calculate what factorial(2) equals. We’ll put 3 * factorial(2) on hold until we know the value of factorial(2).· Goes to outer loop to calculate factorial(2). Once again, does n===1? No, so go to else statement.· Return 2 * factorial (2-1). OK, we need to return return
2 * factorial(1), but I don’t know what factorial(1) is. Luckily, the function has called itself, and we’re now going to calculate what factorial(1) equals. We’ll put 2 * factorial(1) on hold until we know the value of factorial(1).· Goes to outer loop to calculate factorial(1). Once again, does n===1? In this case, it does! So we can finally return a value of 1.· But remember that we had to return 3 * factorial(2)? Luckily, we now know that factorial(2) = 2 * factorial(1), and factorial(1) = 1, so we can return
3 * factorial(2) = 3 * 2 * factorial(1)= 3 * 2 * 1 = 6.
Phew! That was a super long process just to calculate 3! Now imagine if you had to calculate 100891! Hopefully you now understand the mechanism behind recursion, and can also appreciate how computers help us with problems that are beyond the human brain’s capacity!
