Recursion

Indrajeet Mandloi 🧑🏻‍💻 — Tue, 29 Sep 2020 04:06:15 +0000

Most of the time people struggle working with recursive functions. So here is the trick -

A recursive function should always have at least 2 things -

Condition where function ends.
Recursion where function calls itself.

Let's see some examples -

Let's try reversing a string using recursion.

function reverseString(str){
  if (str === '') return '';
  return reverseString(str.substr(1)) + str[0];
}

if (str === '') return ''; this is the condition where function ends/exits. When our string becomes empty it will stop the function.
return reverseString(str.substr(1)) + str[0]; this is Recursion logic where we modify string and call function again with updated string. Let's see the execution of above function for string 'dev'

reverseString('dev'); this will execute in following steps -

reverseString('ev') + 'd';
reverseString('v') + 'e';
reverseString('') + 'v';
if (str === '') return ''

final output would be 'ved'

Sometimes people get confused with when to use recursion and when to use loops. For the above example, we can also use a loop. And of course we can also use a simple javascript str.reverse() method.

But let's see another example where recursion would be the better choice.

Suppose we have a complex nested object and suppose you are generating this object dynamically and you don't know the complexity of object in advance. For example -

const data = {
  'person' : {
     'name' : {
       'fname' : 'Dwight',
       'lname' : 'Schrute'
     },
     'age' : 38
  }
}

Now you need to get the value of 'person.name.fname'. Here the path of the key is string and we don't how nested the key would be. So let's create a function which will return a value -

function findValue(obj, path) {
    const keysArr = path.split('.');
    if (keysArr.length === 1) {
      return obj[parts[0]];
    }
    return findValue(obj[keysArr[0]], keysArr.slice(1).join('.'));
  }

findValue(data, 'person.name.fname'); this will execute in following steps -

1. const keysArr = path.split('.'); // ['person', 'name', 'fname']
2. findValue(obj['person'], 'name.fname');
3. const keysArr = path.split('.'); // ['name', 'fname']
4. findValue(obj['name'], 'fname');
5. const keysArr = path.split('.'); // ['fname']
6. if (keysArr.length === 1) {
      return obj[parts[0]];
    }  // return obj[fname]

final output would be 'Dwight'

If you have any questions or suggestions please let me know. Thank you for reading.

DEV Community: Indrajeet Mandloi 🧑🏻‍💻

Recursion