You already know that it is possible for a function to call another function, and that leads to an interesting question: is it possible for a function to call itself?
The answer is yes, and this method is called recursion. It might sound strange to make a function call itself, but not only it is allowed, this technique can be very useful sometimes.
The most classic example to demonstrate recursion would be the way how exponentiations are calculated.
Two ways to calculate exponentiation
First, let's think about how you would do it with loops. This example calculates a^b:
1function power(a, b) {
2 let result = 1;
3
4 if (b === 0) {
5 return 1;
6 } else {
7 for (let i = 0; i < b; i++) {
8 result *= a;
9 }
10 return result;
11 }
12}
13
14console.log(power(5, 0));
15console.log(power(5, 1));
16console.log(power(5, 2));
17console.log(power(5, 3));11
25
325
4125The power() function first tests if b equals 0 since it is a special case. Any number raised to 0 equals 1. If b is not 0, the function will use a loop to evaluate the exponentiation.
Alternatively, you can go with a recursive solution, which is much more elegant.
1function power(base, exponent) {
2 if (exponent == 0) {
3 return 1;
4 } else {
5 return base * power(base, exponent - 1);
6 }
7}Pay attention to line 5, the function power() called itself with parameters base and exponent - 1. I know this is a bit confusing, but don't worry, to help you understand this code, let's plug in some numbers. Let's calculate 10^5.
For the first step, we simply plug in the numbers, and the function returns 10 * power(10, 4). Then we need to calculate power(10, 4). Plug in the numbers, and we get 10 * power(10, 3), which means power(10, 5) equals 10 * 10 * power(10, 3).
And we keep repeating the same steps until we get 10 * 10 * 10 * 10 * 10 * power(10, 0). Because power(10, 0) returns 1, eventually we get power(10, 5) equals 10 * 10 * 10 * 10 * 10 * 1.
This is a very elegant way of calculating the exponential, as it is very close to the way mathematicians define exponentiation. Unfortunately, this method is about three times slower than using loops in JavaScript.
This is a dilemma that programmers face all the time. We have to choose between simplicity and speed because almost all programs can be made faster by making them bigger. It's up to us to decide on an appropriate balance.
Practical use for recursion
It is true that recursions can be rewritten into loops in some cases, but you should know that recursions are not just an alternative to loops.
Even though it takes some practice, once you get used to using recursions, you will see that some problems are really easier to solve with them, especially those that involve a series of decisions.
For example, consider this problem:
Starting from point 0, you have the options to move along the axis by either moving 2 steps left, or 3 steps right. You should be able to reach any point on the axis by taking the right steps. For example, point 4 can be found by taking 2 steps left, and then 6 steps right.
The question is, how do you find a sequence of steps to take in order to find any random target point, say 25, or -18?
This problem would be difficult to solve if you were using loops, because for every iteration, you have a decision to make: either take 2 steps left or 3 steps right. Instead, let's tackle this problem in a recursive way.
1function find(target, current = 0, history = "") {
2 if (current === target) {
3 return history;
4 } else {
5 return (
6 find(target, current - 2, `${history} - 2`) ||
7 find(target, current + 3, `${history} + 3`)
8 );
9 }
10}
11
12console.log(find(15));
13console.log(find(-15));In this example, we have a target, which points to our target number. A current, which points to the current point on the axis, and it starts from 0. And of course, history, which remembers all the steps current takes to reach the target.
When the function is called, it will first test if current has found the target. If not, this program will have a choice to make: either take 2 steps left and execute the find() function again, or take 3 steps right and then execute find().
The program will repeat this decision over and over again until current equals target, and finally, history will be returned.
That makes sense, right? But unfortunately, when you execute this function, an error will be returned, telling you that the maximum call stack size has been exceeded.
1/Users/. . ./index.js:24
2 if (current === target) {
3 ^
4
5RangeError: Maximum call stack size exceeded
6 at find (/Users/. . ./index.js:24:3)
7 . . .
8
9Node.js v21.5.0In a recursive operation, the state of the previous function call must be retained for every iteration that the function is executed, and JavaScript can only do this for a limited number of times. In our example, JavaScript failed to find the target before this limit was reached.
But 15 isn't a large number, so how did this happen? That is because JavaScript cannot make "smart" decisions like humans. Since we put "going 2 steps left" as the first option, it will keep going with the first option until it finds the target, which will never happen.
The best way to prevent this from happening is to set up a depth control, making sure JavaScript can only go so deep. If it fails to find the target before the depth limit, the program will turn back and try the second option.
1function find(target, current = 0, history = 0, depth = 0) {
2 if (current === target) {
3 return history;
4 } else if (depth === 10) {
5 return null;
6 } else {
7 return (
8 find(target, current - 2, `${history} - 2`, depth + 1) ||
9 find(target, current + 3, `${history} + 3`, depth + 1)
10 );
11 }
12}
13
14console.log(find(15));
15console.log(find(-15));10 - 2 - 2 - 2 + 3 + 3 + 3 + 3 + 3 + 3 + 3;
20 - 2 - 2 - 2 - 2 - 2 - 2 - 2 - 2 - 2 + 3;In this case, JavaScript will first take 2 steps left 10 times, and fail to find the target before the depth limit. Then it will go back 2 steps and try the second option, and if the target is still not found, it will go back again.