[JS “1st timers”] Recursion
This is the 1st timers series.
Today, I’d like to explain “Recursion”.
Honestly, it is quite complicated to understand recursion. I repeat myself many times in this article, but that’s what recursion is all about.
Please be patient and read it slowly.
The definition of Recursion is “a function that returns itself”. In my previous post, I explained about “closure” which returns function with the variable. While they look similar, closure returns a function that has not been invoked yet.
However, in the case of recursion, it returns it’s own function and invokes it too.
Basically, it looks like the gif below. (Don’t look at it so much, it will make you sick…)
Let’s have a look at the example below.
(You might want to take a screenshot/or just write down the snippet below and read this article while looking at it.)
There is a function add. It is invoked with an argument 3 in line 9.
There is the if statement in the function, and after else keyword in line 5, the function add returns x + add(x - 1).
What is that? We know x is 3 because it is invoked add(3).
But what is add(x-1)?
It means the function add is invoked with an argument which is x -1 in the return statement.
In the example, x is 3, so add(x - 1) is the same as add(2).
x + add(x-1) === 3 + add(2);
//I invoked the function add(3) so "x" = 3;In JavaScript, a function name with parentheses means invoking a function.
So, in line 5, the function add is invoked with an argument 2 in the return statement of the function add.
What is going to happen?
The function add invoked the function add itself with the argument 2, so we go back line 1, and run the function add again! (2nd implementation)
In the 2nd implementation, the variable x is 2.
The condition (x === 0) is still false, so line 2 and 3 are ignored, and we go to line 5.
Oh, again?
Yes, we come back to line 5 and the 2nd implementation of add returns the function add with an argument(x - 1) and invoked.
//2nd implementation "add"x + add(x-1) === 2 + add(1);
//I invoked the function add(2) so "x" = 2;
Then, we go back to line 1, and run the function “add” again! (3rd implementation)
In the 3rd implementation, the variable x is 1.
It is still false in the condition (x === 0), so line 2 and 3 are ignored and we go line 5.
Oh, again?
We are in line 5 again, and the 3rd implementation of add returns the function add with an argument(x - 1) and is invoked.
//3rd implementation "add"x + add(x-1) === 1 + add(0);
//I invoked the function add(1) so "x" = 1;
Then, we go back line 1, and run the function add again! (4th implementation)
In the 4th implementation, the variable x is 0.
Finally, the condition(x === 0) is true, and we go line 2 and 3.
In line 3, the function add returns 1.
Great! We get an answer!
//4th implementation "add"if(x === 0){
return 1;
//x is "0" and it matches with condition! So, return "1".
Great, but… we’re still halfway of complete recursion.
The function add returns a result which is 1. But, what is this result for?
Remember, we implemented the function add 4 times.
And, the computer remembers every single step.
This is called call stack. The computer stacks every single step when the function is invoked and removes every stack when its return action has been completed.
In the 4th implementation, the function add returns 1 and it is completed, so the 4th implemented of add is removed from the call stack, but we still have 3rd, 2nd, and 1st implementation of add in the call stack because these return has not been completed yet.
//4th implementation "add"const add(0) => {// x - 1 is "0" it is invoked from add(1 - 1);
if(x === 0){
return 1; // x === 0 is true, return 1. Complete!
} else {
return x + add(x - 1);
};
};
What is the return value of the 3rd implementation of add?
It is x + add(x - 1).
//3rd implementation "add"x + add(x-1) === 1 + add(0);
But, we know add(0) has already returned value 1.
So, it has a small change.
//3rd implementation "add"x - add(x-1) === 1 + 1; // return "2"
Oh, we got an answer! add(1) returns 2.
Then, the 3rd implementation of add is removed from the call stack.
Good… what is next?
Yes, we should go to the 2nd implementation of add.
//2nd implementation "add"x + add(x-1) === 2 + add(1);
We know add(1) returns 2.
//2nd implementation "add"x + add(x-1) === 2 + 2; // return "4"
So, the return value of add(2) is 4.
Then, the 2nd implementation of add is removed from the call stack.
We are almost the goal.
Go back to the 1st implementation of add.
//1st implementation "add"x + add(x-1) === 3 + add(2);
We know add(2) returns 4.
//1st implementation "add"x + add(x-1) === 3 + 4; // return "7"
And below is the full snippet of the 1st implementation.
//1st implementation "add"const add(3) => {
if(x === 0){
return 1;
} else {
return 3 + 4; which is "7", complete!
};
};
Finally, we got an answer which is 7, and the 1st implementation of add is removed from the call stack, Mission complete!
This is how recursion works, and it tempts you to the labyrinth.
The key point of recursion is “the function invokes itself until the very end of the function”.
The below movie shows the whole process that I explained.
(You might want to keep the snippet and watch it while looking at it.)
One last thing.
You should be careful about setting the endpoint when you run recursion.
In the example statement “ if(x===0){ … ” is the endpoint.
Otherwise, the function will be invoking the function again and again, and never stop.
The function invokes itself and the invoked function invokes itself and the invoked function invokes itself…
This is called an infinite loop, and it will crash your browser. You have to kill it once that happens.
I hope you learned a little about recursion from my articles.
Thanks for reading!
