# EXPLAINING RECURSION IN JAVASCRIPT
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.

## INTRODUCTION
In this article you learned the following:
* What the concept of recursion is in programming
* The 2 rules of recursion
* How to use a recursive function to get value from a deeply nested object
* How to create a deep copy of an object recursively.

## TABLE OF CONTENT
* WHAT IS RECURSION
* RULES FOR RECURSION
* Base Case
* Recursive Case

* CALLSTACK AND RECURSION

* APPLYING RECURSION
* Reading a deeply nested object

* CONCLUSION
* Summary

 
 

## WHAT IS RECURSION
> *“To understand recursion, one must first understand recursion.*”
> —Stephen Hawking

 
In math, linguistics, and art, *recursion* refers to the occurrence of a thing defined in the 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.)

<div>
<img src = "https://cdn.kastatic.org/ka-perseus-images/0486791ea01a5456299a6f441a4487a10d12d9da.jpg">
<center> <small><i>Russian doll—real life example of recursion</i> <br/> credit: <a style="color:#333; text-decoration: underline" href='https://www.khanacademy.org/computing/computer-science/algorithms/recursive-algorithms/a/recursion'>khanacademy</a></small></center>
</div>

&nbsp;
&nbsp;

## RULES FOR RECURSION

For recursive functions to be implemented correctly, they must follow specific rules so that [Stack overflow](https://en.wikipedia.org/wiki/Stack_overflow_(disambiguation)) is avoided.

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

 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 calling itself. In the `countDownToZero` example, `countDownToZero(n-1)`; is where the recursion actually happens.

 function countDownToZero(n) {
     .....
     // recursive case
     } else {
         console.log(n);
         countDownToZero(n - 1) // count down 1
     }
 }

countDownToZero(5);

&nbsp;
&nbsp;

## THE CALLSTACK AND RECURSION
When a function calls itself recursively it gets added to the call stack. Stacks are LIFO (Last In First Out) structures, meaning that the last item that was added to the top of the stack is the first one to be removed from the stack later on.

Let's see how the Stack handles our `countDownToZero` recursive function:

 function countDownToZero(n) {
     // base case. Stop at 0
     if(n < 0) {
         return; // stop the function
     } else {
         console.log(n);
         countDownToZero(n - 1)
     }
 }

countDownToZero(5);


This is the reason why a base case is important, without a base case an infinite loop occurs which will cause stack overflow.

&nbsp;
&nbsp;
## APPLYING RECURSION
In Javascript most problems that can be solved with a recursive approach, also have an iterative approach that can be used to solve them. That being said, recursion easily solves problems when working with tree structures. A deeply nested object is a tree structure.

### READING A DEEPLY NESTED OBJECT FIELD

 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.

get(person, 'data.name.last_name', 'unknown');

This utility safely tries to read the value and, if it doesn't exist returns the `'unknown'` string.

Here is what the implementation of such a utility may look like using a recursive function:

 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 till it reaches the last part of the path. 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`.

### COPYING AN OBJECT (DEEP COPY)
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 either the source or the copy may also cause the other object to change too (because the two objects share the same references).

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

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 an array/object
  }

  return copy;
};

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**

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**

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 it evaluates to `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`.
* Then 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 calling the `createDeepCopy()` function for each element in our reference object(the object we are copying from) recursively. If the data type of the element is a primitive data type it will be returned as it is else `createDeepCopy()` will be called recursive until it reaches the base case.

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

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 `deepcCpied` 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)**

&nbsp;
&nbsp;
## CONCLUSION
With the basic understanding of recursion you now have, 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.

### Summary

In this article you learned the following:
* What the concept of recursion is in programming
* The 2 rules of recursion
* How to use a recursive function to get value from a deeply nested object
* How to create a deep copy of an object recursively.