Hello there.
Let’s have a look at what Recursion is supposed to be in Data Structures & Algorithm.
It is an undeniable fact that we can’t talk about DSA without mentioning recursion along the way, recursion forms most part of solving many of DSA problems. now let’s take a look at Recursion.
What is Recursion in DSA ?
Recursion in a simple term is just a function that calls itself to repeat a task until it’s done. let’s think of it this way. if for some reasons decide to climb a very tall mountain am very sure you can’t just start speeding up and within seconds get to the top of the mountain. well that can be done if you tell me you’re Superman. in my opinion the wise way to accomplish this task is to climb the mountain in bit and take some pauses and continue right after that. unfortunately recursion won’t take a pause instead right after the short work in lieu of pausing it then looks for the next task and chains after until it finishes it’s job. now notice that recursion will never stop working if you don’t ask it to do so or the infrastructure on which it’s running blows up. so for that matter remember you always need to specify when the recursion should stop working and this process is what we call the Base case or exit plan if you want it that way, it actually doesn’t matter anyway. Recursion is just an alternative to iteration with a for loop. A very simple example of a recursive function is written bellow.
function countDown(number){
if(number < 0) return 0;
console.log(number);
recursion(number - 1)
}
recursion(5);
There you go, now let’s digest this a little bit. the name of the function is countDown, the if Statement is our escape plan you remember Base case ? at this level we’re are saying when the function runs and the value of number is less than zero ? then the function should return 0 and stop fooling around. But before then there is a task it needs to perform which is at every run before the number reaches Zero it should keep printing console.log(number) it has at the moment then after that substract 1 from that number and repeat the same process until it hits Zero, that is exactly the task given and it will execute that without complaining. Now you might be wondering how the function knows the previous number and it’s simple. With recursion the function keeps the last result in memory so it’s no big deal for it to know the last printed result is …. ?
Remember i said Recursions are just alternatives to For Loop ? let’s re-write the same function for the same output with the following.
function countDown(number){
for(i=0;i<=number.length;i++){
console.log(i)
}
}
recursion(5);
Here our base case has been specified already in the for loop where we said i<=number.length so it will keep printing the i until it’s less or equal to the provided number which is 5 in this case.
Another popular problem recursion can easily solve is Factorial Problems. ie. Find the factorial of the given number.
function factorial(num) {
if (num === 1) return 1;
console.log(num);
return num * factorial(num - 1);
}
factorial(5)//1*2*3*4*5=120
The rule of factorial says, multiply all the numbers found between 0 and a given number and in this case we provided 5 so the final answer should be 120. This same function can be achieved using a for loop to arrive at the answer. Try to write it on your own to see if you can get it.
You can equally try the sumRage of a number as well below is the recursive function of the problem.
function sumRange(num) {
if (num === 1) return 1;
return num + sumRange(num - 1);
}
sumRange(5);
I believe by now recursion has made a little bit more sense with my baby explanation. Once you get your head around it by practicing more problems. it will all click in your head and you will never have to worry about it anymore.
Alright we have to say later now. Stay safe and solve more questions.