Recursion is when a function calls itself until it is stopped, otherwise it continues to call itself forever. A function that does this is called a recursive function. It usually has this syntax:
function recurse() {
if (condition) {
// stop recursion
} else {
recurse();
}
}
A cool benefit of recursion is that it is a more elegant way to perform a unit of work multiple times.
There are three key features which should be in a recursive function:
A Termination Condition: It is put there to prevent the recursive function from running if there's bad input from the user.
A Base Case: This is a condition that stops the function from running forever. The base case is the goal of the recursion. That is, the function will continue to run until its output matches the condition in the base case. Base cases are usually within an
ifstatement. Something likeif (this happens) {yay! we're done};.The Recursion: This is the main recursive statement in the function.
Let's take a look at a very popular example of recursion:
Write a function that returns the factorial of a given integer.
For starters, in mathematics, a factorial is the product of an integer and all the integers below it. What this means is, if we are given a number - let's say 4 - and asked to find its factorial, we would multiply 4 by all positive integers below it (or less than it). Positive integers less than 4 are 3, 2, 1. So the factorial of 4 will be
4 * 3 * 2 * 1 = 24.
The function for this will be:
function factorial(x) {
if (x < 0) return;
if (x === 0) return 1;
return x * factorial(x - 1);
}
Now let us identify the three key features of the function factorial(x):
The first one is:
if (x < 0) return;
What this statement does is to prevent the function from running if the user inputs any value lower than 0. This is the termination condition.
The second one is:
if (x === 0) return 1;
This statement is the base case. The function checks if the number put in by the user is strictly equal to 0, and then it returns 1. At this point, due to the nature of the third statement and the first, the function will stop executing and return its output.
If the user puts in any number greater than 0, it will execute the third statement first:
return x * factorial(x - 1);
This is the recursive function itself. It will continue to run until it reaches the base case, at which point it will stop, and return its output.
With all these in place, if we pass a number into the function, something like factorial(4), this is what will happen:
- Since 4 is greater than 0, it will ignore the first statement, and since it is also not equal to 0, it will ignore the second statement and go straight to the recursive function, which will then return
4 * factorial(3);
// 4 * factorial(4-1);
factorial(3)which is inside4 * factorial(3);will also run and return
3 * factorial(2);
// 3 * factorial(3-1);
factorial(2)which is inside3 * factorial(2)will then run and return
2 * factorial(1);
// 2 * factorial(2-1);
factorial(1)inside2 * factorial(1)will then run and return
1 * factorial(0);
// 1 * factorial(1-1);
factorial(0)itself will run, and since the base case isif (x === 0) return 1, it will return 1, then it will stop.
Once the function stops running, it then returns the results of the nested functions starting from the base case.
Like this:
factorial(4) returns 4 * factorial(3);
factorial(3) returns 3 * factorial(2);
factorial(2) returns 2 * factorial(1);
factorial(1) returns 1 * factorial(0);
factorial(0) returns 1;
/* Now that we've hit our base case,
our function will return in order from inner to outer */
factorial(0) returns 1 => 1;
factorial(1) returns 1 * factorial(0) => 1 * 1;
factorial(2) returns 2 * factorial(1) => 2 * 1 * 1;
factorial(3) returns 3 * factorial(2) => 3 * 2 * 1 * 1;
factorial(4) returns 4 * factorial(3) => 4 * 3 * 2 * 1 * 1;
// 4 * 3 * 2 * 1 * 1 = 24;
This is because when you have nested function calls, the most inner nested function returns first. This initiates the ‘unwinding’ as they return in order.
I hope this has helped you understand recursion in JavaScript. If you still need more clarity, drop a comment and I'll do my best to explain it... Thank you.
These articles helped me understand recursion and write this article, and I know they'll help you too... Kindly check them out 👇
Learn and Understand Recursion in JavaScript
A Quick Intro to Recursion in JavaScript