So I’ve been learning to code in Javascript for the past month now and the course on Codecademy was a very good way to start the process, so if you’d love to get started with JS I am sure Codecademy is the place for you. After the course on Codecademy, I decided to take a step further; I started reading Marijn Haverbeke’s book Eloquent JavaScript and I must say it’s a very good book. But while reading it I stumbled on the first concept that gave me a bit of a headache RECURSION, And that’s what this blog post is about so let’s get to it.
In simple terms, recursion is when a function calls itself and any function that does this is called a recursive function. The main reason why you might use a recursive function is when you want to repeat a procedure over and over till a certain condition is met. Now you might ask “ Why not use a simple for-loop or a while-loop? ”, Well the truth is using a for loop or while loop is actually better than writing a recursive function; I mean the loops are three times faster than recursive functions and the only upside to a recursive function is that it is more human readable. According to Marijn Haverbeke, There is a/the dilemma of speed versus elegance. If your function is simple to understand please go on and use a regular loop but some complicated functions written with loops could get rather annoying and hard to understand I’d advice to just go for a recursive function as far as it does not overflow the stack in the process. That is enough talk let’s take some examples shall we?.
I’ll be using one of the most popular examples on the internet. We will go through a function to find the factorial of a given number.
Factorial Function
I’ll assume we all know what the factorial of a number is, for those of us who don’t know (myself before finding out), the factorial of a number is simply the multiplication of the said number by itself minus one until you reach the number 1.
Example: The factorial of the number 5 is 5*4*3*2*1 which is also equal to 120.
A lot of what I have written on this topic was heavily influenced by this blog post.
let factorial = (n)=>{
if(n<0){
return;
}else if(n === 0){
return 1;
}else{
return n * factorial(n - 1);
}
}
console.log(factorial(3));
// 6
This is what a typical recursive function to find the factorial of a given number in Javascript would look like. Let’s go through it. When the function is called there are a few conditions to be checked,
/*
The first condition in the block of code within the function being this.
***Termination condition aka WASH***
*/
if(n < 0){
return;
}
This block checks if the argument ’n’ passed into the function is less than 0 and if so it will return nothing, the reason being, we can’t find the factorial of a negative number ( well I don’t think we can ).This condition is known as the termination condition aka ‘wash’
/*The next condition in block of code
***Base condition aka RINSE***
*/
else if(n === 0){
return 1;
}
The next condition after the termination condition checks if the integer ’n’ is equal to 0 and if so that means we’ve reached the goal our recursive function and it returns 1 ( the value to stop when finding factorials ).This condition is known as the base condition aka ‘rinse’.
The last part of the conditional statement is where all the magic happens.
// magic!!... where the function calls itself
else{
//***The recursion aka REPEAT***
return n * factorial(n - 1);
}
Now what happens here is that if the first two conditions are false this will run by default. The weird thing here is our function calling itself but with an argument 1 less than the initial value of ’n’. This line here is what makes this whole function recursive. This line is the recursive condition aka ‘repeat’.
Let’s go through what’s happening here.
How it works
We call the function and pass in the value of 4.
factorial(4);
The two if statements in the function fail since 4 obviously isn’t less than 0 or equal to 0. So the default condition is run. This returns the integer 4 multiplied by the factorial(4 –1).
return 4 * factorial(3);
Now what happens after that is the function repeats itself within this line with the new argument as 3 ( Which is the result of 4 –1) and again the factorial function checks if the 3 is less than 0 or equal to 0, this check returns false again but this time it gives return 3 * factorial(3 - 1);
return 3 * factorial(2);
The same process happens again. The factorial function checks if 2 is less than 0 or equal to 0 and since these conditions return false again we fall right into the recursive part and it gives return 2 * factorial( 2– 1)
return 2 * factorial(1);
And the process repeats itself, 1 is obviously not less than 0 or equal to 0 so we dive into the recursive part again and it gives return 1 * factorial(1–1)
return 1 * factorial(0);
Now the conditions in the factorial function check again and we find that 0 is not less than 0 for the first condition but 0 is definitely equal 0 for the second condition and what happens here is that the function returns 1
else if(n === 0){
return 1;
}
Now when you think about it there should be a return 0 * factorial(0) right? well, there is but since factorial(0) returns 1 multiplied by 0 (1 x 0) is equal to 0 this part is never run. Remember when I said the function will run till a certain condition is met? Well, the condition we set as the base condition (aka RINSE) is where the function is expected to stop running and compute the values.
So for every time, the function was passed an argument greater than 0 the line happensreturn n * factorial(n — 1). And ’n’ multiples the return value of the function, to put this all together to make a bit of sense we read it in reverse (starting from factorial(0))
factorial(0) returns 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,
And at the end of it, we have this function returning.4*3*2*1*1 which is equal to 24
The End
I really hope my first ever blog post helped you understand this concept and if it didn’t I am very sorry for being a crappy blogger but on the bright side I found this good recursion yo mama joke on DevRant(I don't intend to offend anyone). If you got this far you deserve a good laugh
Big thanks to Tobey, Godspeed, and Kratos for helping me understand this better and writing this blog post
Top comments (0)