Recursion is an essential topic in the area of functional programming. Newbie programmers often find it challenging to understand what it is and how it works. So, I'll try to make recursion easy for you. At least, will try to clear your basic understanding about the topic. So, let's get started 😁.
Gif from Giphy
What is Recursion?
If you search "recursion" in Google, every time you'll get a message "Did you mean: recursion". And every time you click on the Did you mean link, it'll again show you the same. And this is after all what recursion actually means, Calling something again and again.
In terms of computer programming, a recursive function is a function that calls itself until it satisfies some exit condition. Otherwise, we'll be stuck into an infinite loop or in case of JavaScript, the call stack will be overflowed. Let's see an example to understand it better.
We all know what a factorial is. We get factorial of a number if we continue multiplying the number itself with a value smaller than it until we reach 1.
For example, the factorial for number 3 will be, 3 2 1 = 6.
Here's a function that returns the factorial of a number.
function factorial(r) {
if(r <= 0) return 1;
else return r*factorial(r-1);
}
console.log(factorial(3));
We are passing the number with the parameter r. How is this a recursive function? If you look at the else condition, you'll find that it is calling the function itself until it matches the exit condition which is r <= 0.
You can imagine that the same can be achieved using a loop. And you are right. Here is the same function using a loop.
function factorial(r) {
let factor = 1;
for(let i = r; i > 1; i--) {
factor *= i;
}
return factor;
}
console.log(factorial(3));
Rather, using a loop will be a better choice in case of such small functions. In JavaScript running a loop is generally cheaper than calling a function multiple times. The time complexity will be higher with a recursive function. But there are multiple instances where loops are not worth. They make the function more complex. And, any recursive function can be implemented using loops.
Now that we know what a recursive function is let's move on to building a recursive function by ourselves.
Creating a Recursive Function
One most important thing to keep in mind while working with recursive function is to Declare a termination condition. Otherwise, our function will overflow the call stack.
How do we declare a termination condition? Most simply, we can put it inside an if statement.
Here in this example, suppose we want to write a recursive function that returns the sum of a given range. So, if we pass 3, it will output the sum of the range from 1 to 3, i.e., 1 + 2 + 3 = 6.
Step 1: Declare a function name. It'll take a single parameter which will specify the range. Feel free to use arrow functions if you want.
function sumRange(r){
}
Step 2: Declare a termination statement. When do we want this function to exit? When our range is 0, right?
function sumRange(r) {
if(r <= 0) return 0;
}
Step 3: Your logic where the magic happens.
What do we want to achieve here? We want to do (current range + (range-1)) in a loop until our range becomes 0. We are getting the current range from r. How do we get the (range-1)? We call the function again and again by passing the parameter as (r-1).
function sumRange(r) {
if(r <= 0) return 0;
return r+sumRange(r-1);
}
The function flow:
First, we call our function by passing the value 3.
sumRange(3);
The above call runs the function. First, it checks the if statement. Finding it false, it'll continue to work with the else. At else, we return 3 + the value of sumRange(3-1).
return 3 + sumRange(2);
The above logic also works here. Except that, this time, our range was 2. So, it'll return 2 + sumRange(2-1)
return 2 + sumRange(1);
Same happens again. Now the range is 1. So the returning sumRange will be (1-1).
return 1 + sumRange(0);
When the range becomes 0, our if condition will run and it will return 0.
Now that all our function calls has returned a value, everything will start to unwind. The innermost function will return first.
So, sumRange(0) will return 0.
sumRange(1) will return 1 + sumRange(0) or, 1 + 0 = 1
sumRange(2) will return 2 + sumRange(1) or, 2 + 1 + 0 = 3
sumRange(3) will return 3 + sumRange(2) or, 3 + 2 + 1 + 0 = 6 and we get the answer 6 and we are done.
If you read the article to this point, a big thank you 😊. I hope you get some basic understanding of how recursion works and how to write a recursive function.
