Explaining Recursion in JavaScript
Tags: javascript, programming, functional, algorithms
Published: 2022-10-12 22:51:26

by [Eni Onyedikachi](https://blog.openreplay.com/authors/eni-onyedikachi)

In math, linguistics, and art, *recursion* refers to the occurrence of a thing defined in terms of itself. In computer science, recursion refers to a function that calls itself. Recursive functions solve complex problems through the "divide-and-conquer" method(a method to solve problems that consist of solving smaller portions of the same problem until you solve the original, larger problem.)

![Russian doll—real-life example of recursion](https://blog.openreplay.com/images/explaining-recursion-in-javascript/images/image01.jpg)

Recursion is no doubt one of the oldest concepts in programming. It's the paradigm where a function calls itself. This technique is usually used to solve problems that require breaking them into smaller subproblems. In this article, we'll discuss recursion and show examples of its application.


## Two basic cases

For recursive functions to be implemented correctly, they must have two cases, so that [Stack overflow](https://en.wikipedia.org/wiki/Stack_overflow_(disambiguation)) is avoided and computation finishes correctly.

### Base Case

The base case (also known as the terminating case) stops a function from calling itself when a given condition is reached.

For example, check out the following function, which prints numbers counting down from *n* to 0:
```javascript
 function countDownToZero(n) {
     // base case. Stop at 0
     if(n < 0) {
         return; // stop the function
     } else {
         console.log(n);
         countDownToZero(n - 1)
     }
 }

countDownToZero(5);
```

output:
```
// 5
// 4
// 3
// 2
// 1
// 0
```
In the preceding code, the base case is when `n` is smaller than `0` because we want to stop counting at `0`. If a negative number is given as the input, the `countDownToZero` function will not print that number because of the base case.

### Recursive Case
Simply stated: Our function is calling itself. In the `countDownToZero` example, `countDownToZero(n-1)`; is where the recursion actually happens. 
```javascript
 function countDownToZero(n) {
     .....
     // recursive case
     } else {
         console.log(n);
         countDownToZero(n - 1) // count down 1
     }
 }

countDownToZero(5);
```





## The call stack and recursion

When a function calls itself recursively, it gets added to the call stack. [Stacks](https://en.wikipedia.org/wiki/Stack_(abstract_data_type)) are LIFO (Last In, First Out) structures, meaning that the last item added to the stack is the first one to be removed from the stack later.

Let's see how the Stack handles our `countDownToZero` recursive function:
```javascript
 function countDownToZero(n) {
     // base case. Stop at 0
     if(n < 0) {
         return; // stop the function
     } else {
         console.log(n);
         countDownToZero(n - 1)
     }
 }

countDownToZero(5);
```
![2](https://blog.openreplay.com/images/explaining-recursion-in-javascript/images/image02.png)

This is why a base case is critical: without a base case, an infinite loop will cause a stack overflow.



<h2>Open Source Session Replay</h2> 

_<a href="https://github.com/openreplay/openreplay" target="_blank">OpenReplay</a> is an open-source, session replay suite that lets you see what users do on your web app, helping you troubleshoot issues faster. OpenReplay is self-hosted for full control over your data._

![OpenReplay](https://blog.openreplay.com/banner-blog_1oYPGT.png)

_Start enjoying your debugging experience - <a href="https://github.com/openreplay/openreplay" >start using OpenReplay for free</a>._





## Applying Recursion

In programming, all problems that can be solved with a recursive approach also have an iterative approach that can be used to solve them. That being said, for many problems recursion provides a much easier solution. An example is working with tree structures, such as deeply nested objects.


### Reading a deeply nested field

Let's assume we have an object like the following, and we want to access a deeply nested field within the object:

```javascript
 const person = {
     data: {
         age: 20,
         name: {first_name: "John", last_name: "Doe"},
     }
 }
 
 console.log(person.data.last_name)
```
Output:
```
undefined
```
We want to read the `last_name` of `person`. We have to write `person.data.last_name`. And, of course, if some data is missing, we will get `undefined`.

To solve this problem, we use helpers like [lodash's](https://lodash.com/) `get` method.

```javascript
get(person, 'data.name.last_name', 'unknown');
```
This utility safely tries to read the value and returns the `'unknown'` string if it doesn't exist.

Here is what the implementation of such a utility may look like using a recursive function:
```javascript
 function get(obj, path, fallback) {
     const parts = path.split(".");
     const key = parts.shift();
     if(typeof obj[key] !== "undefined") {
         return parts.length > 0 ? get(obj[key], parts.join("."), fallback) : obj[key];
     }
     return fallback;
 }

console.log(get(person, "data.name.first_name"));
console.log(get(person, "data.name.last_name"));
console.log(get(person, "data.age"));
console.log(get(person, "data.date_of_birth"));
console.log(get(person, "data.date_of_birth", false));
```
Output:
```
John 
Doe
30
undefined
false
```
Notice how `get` calls itself recursively until it reaches the path's last part. Also, the `fallback` parameter is returned when we try to read a value that doesn't exist—`console.log(get(person, "data.date_of_birth"))` returns `undefined` which is the default value when a `fallback` is not provided. When a `fallback` is provided, the provided value is returned—`console.log(get(person, "data.date_of_birth", false));` returns `false`.



### Doing a deep copy of an object

As per [MDN](https://developer.mozilla.org/en-US/docs/Glossary/Deep_copy#:~:text=A%20deep%20copy%20of%20an,which%20the%20copy%20was%20made.):

>A deep copy of an object is a copy whose properties do not share the same references (point to the same underlying values) as those of the source object from which the copy was made. As a result, when you change either the source or the copy, you can be assured you're not causing the other object to change too; that is, you won't unintentionally be causing changes to the source or copy that you don't expect. That behavior contrasts with the behavior of a shallow copy, in which changes to the source or the copy cause the other object to change (because the two objects share the same references).

Let's see how to create a deep copy of an object using recursion.

```javascript
const createDeepCopy = (input) => {
  if (typeof input !== "object" || input === null) {
    return input; //BASE CASE
  }
    
  let copy = Array.isArray(input) ? [] : {};
    
  for (let key in input) {
    const value = input[key];
    copy[key] = createDeepCopy(value); //recursive call for each element of 
};


```

In the preceding code `createDeepCopy()` is  a recursive function. It creates a deep copy of an object passed to it through its `input`  argument.


### Base Case

```javascript
if (typeof input !== "object" || input === null) {
    return input; //BASE CASE
  }
```

In the preceding code, if the `input` is a primitive [type](https://blog.openreplay.com/javascript-types-and-values-explained/)(string, number, etc.) or equal to a `null` value it is returned, this ensures only objects that are not `null` are passed in as input. 

### Recursive Case

```javascript
let copy = Array.isArray(input) ? [] : {};
    
  for (let key in input) {
    const value = input[key];
    copy[key] = createDeepCopy(value); //recursive call for each element of an array/object
  }

  return copy;
```

For the recursive case:
*  The copy of the object is stored in the `let copy;` variable.
*  Then we check if the object is an array or an object `let copy = Array.isArray(input) ? [] : {};`, if `true`, a copy of an empty array is initialized; else, a copy of an empty object is initialized.
*  Then loop through the object's `keys`(object) or `indexes`(array) using a `for in` loop.
*  The corresponding `key` or `index` value is stored in the `value` variable—`const value = input[key];`.
*  The `createDeepCopy(value)` function is called recursively with `value`. 
* The result is stored with the same key name in our copy object—`copy[key] = createDeepCopy(value)`.
* Our object copy is returned—`return copy;`.

We are essentially recursively calling the `createDeepCopy()` function for each element in our reference object(the object we are copying from). If the data type of the element is primitive, it will be returned as it is; else, `createDeepCopy()` will be called recursive until it reaches the base case.


For example, let's pass an object into the `createDeepCopy()` function to get its deep copy equivalent.

```javascript
let originalCopy = [
  undefined,
  null,
  "Hello",
  20,
  {
      location: {
          city: "new york",
        },
  },
];

let deepCopied = createDeepCopy(originalCopy);

deepCopied[2] = "Bonjour"
deepCopied[3] = 30
deepCopied[4].location.city = "lagos"


console.log(deepCopied, originalCopy);
```

Output:
```
/// New Copy
[ undefined, null, 'Bonjour', 30, {location: { city: 'lagos' } } ]

/// Original Copy
[ undefined, null, 'Hello', 20, {location: { city: 'new york' } } ]
```

In the preceding code, we can verify that the object passed into `createDeepCopy()` is actually copied. From the output, the values changed in the `deepCopied` object are not reflected in the object they are copied from(`originalCopy`). View the Demo **[Here](https://stackblitz.com/edit/js-ikoigd?devToolsHeight=33&file=index.js)**





## Conclusion

With the basic understanding of recursion, it can now be used as part of your problem-solving arsenal as a developer—especially for problems that require breaking them into smaller subproblems.

> A TIP FROM THE EDITOR: Don't miss our [Forever Functional: Solving Puzzles With Recursion And JavaScript](https://blog.openreplay.com/forever-functional-solving-puzzles/) article, with several more examples of recursion application.




[![newsletter](https://blog.openreplay.com/newsletter_Z1P0UIP.png)](https://newsletter.openreplay.com/)