Introduction to Recursion in JavaScript
Tags: javascript
Published: 2020-09-24 14:58:58

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 😁. 
![](https://media.giphy.com/media/XkDyB1jCZMxUs/giphy.gif) *Gif from [Giphy](https://giphy.com/)*

## 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.

![](https://i.ibb.co/8BLS70r/recursion-1.png)

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.

  ```javascript
function factorial(r) {
    if(r <= 0) return 1;
    else return r*factorial(r-1);
}
console.log(factorial(3)); //6
  ```

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.

```javascript
function factorial(r) {
    let factor = 1;
    for(let i = r; i > 1; i--) {
        factor *= i;
    }
    return factor;
}
console.log(factorial(3)); //6
```

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.

```javascript
function sumRange(r){
    
}
```

**Step 2:** Declare a termination statement. When do we want this function to exit? When our range is 0, right? 

```javascript
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).

```javascript
function sumRange(r) {
    if(r <= 0) return 0;
    return r+sumRange(r-1);
}
```

## The function flow:

1. First, we call our function by passing the value 3.

   ```bash
   sumRange(3);
   ```

2. 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)`.

   ```bash
   return 3 + sumRange(2);
   ```

3. The above logic also works here. Except that, this time, our range was `2`. So, it'll return `2 + sumRange(2-1)`

   ```bash
   return 2 + sumRange(1);
   ```

4. Same happens again. Now the range is `1`. So the returning `sumRange` will be `(1-1)`. 

   ```bash
   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.