Learn and Understand Recursion in JavaScript
I’ll walk you through two popular JS recursion examples in 10 minutes so you can finally understand how recursion works in JavaScript.
What is Recursion?
Recursion is simply when a function calls itself.
Lets jump right in and take a look at probably the most famous recursion example. This example returns the factorial of a supplied integer:
function factorial(x) {
if (x < 0) return;
if (x === 0) return 1;
return x * factorial(x - 1);
}
factorial(3);
// 6
Woah. It’s Okay if that makes no sense to you.The important part is happening on line 4:return x * factorial(x — 1);
. As you can see the function is actually calling itself again (factorial(x-1)
) but with a parameter that is one less than when it was called the first time. This makes it a recursive function.
Before I break down that code example any further, it’s important you understand what factorials are.
To get the factorial of a number you multiply that number by itself minus one until you reach the number one.
Example 1: The factorial of 4 is 4 * 3 * 2 * 1 or 24.
"Example 2: The factorial of 2 is just 2 * 1 or "2.
Awesome now that our High School Math lesson is over we can return to the good stuff!
The three key features of recursion
All recursive functions should have three key features:
A Termination Condition
Simply put: if(something bad happend)[ STOP };
The Termination Condition is our recursion fail-safe. Think of it like your emergency brake. It’s put there in case of bad input to prevent the recursion from ever running. In our factorial example if(x < 0) return;
is our termination condition. It’s not possible to factorial a negative number and thus we don’t even want to run our recursion if a negative number is input.
A Base Case
Simply put: if(this happens) [ Yay! We're done };
The Base Case is similar to our termination condition in that it also stops our recursion. But remember the termination condition is a catch-all for bad data. Whereas the base case is the goal of our recursive function. Base cases are usually within an if statement. In the factorial example if(x === 0) return 1;
is our base case. We know that once we’ve gotten x down to zero we’ve succeeded in determining our factorial!
Simply put: Our function calling itself. In the factorial examplereturn x * factorial(x — 1);
is where the recursion actually happens. We’re returning the value of the number x multiplied by the value of whateverfactorial(x-1)
evaluates to.