CODEWITHSUNDEEP
javascriptstringrecursionreverse
theodore braden
theodore braden

Reputation: 39

what is actually going on when reversing a string using recursion

I'm relatively new to Javascript. I understand recursion conceptually and see its value. However, i find myself a little confused about what actually happens. I know this isn't the easiest way to reverse a string. But i'm using it as an easy example 

function reverse(str){
if (str === ""){ 
   return ""; 
   } else { 
       return reverse(str.substr(1)) + str.charAt(0); 
    } 
  }

So hows does a string like "hello" become "olleh" when the code is telling us to recursively place the first character at the very end of the string as in (elloh)? Hope my question makes sense. Thanks in advance

Upvotes: 0

Views: 211

Answers (4)

theodore braden
theodore braden

Reputation: 39

I get it. So it's taking away letters from the string and returning them in reverse order until the original string is empty.

Thanks so much!

Upvotes: 0

gtgaxiola
gtgaxiola

Reputation: 9331

Calling reverse("hello")

The Recursive Call is 

      Function Call                     Returning string
return reverse(str.substr(1))    +        str.charAt(0);

Following it on each step

     Recursive Calls                              Returning strings
       reverse("ello")                                  + "h";
           reverse("llo")                          + "e"
               reverse("lo")                  + "l"
                   reverse("o")          + "l"
                       reverse("")  + "o"

No more recursion return the sub-solutions

                + "h";
            + "e"
        + "l"
    + "l"
+ "o"
-----------------------------
"o"+"l"+"l"+"e"+"h"  =         "olleh"   ("hello" reversed)

Upvotes: 1

A.Roehl
A.Roehl

Reputation: 91

This function puts the first char of the given string at the end of the 'return' statement. Afterwards, the function is called recursivly by deleting the first character of the old string and do the same thing again. The iterations would look like this:

input Word: 'hello'

first iteration: return reverse('ello') + 'h' // returned word until now: 'h'
second iteration: return reverse('llo') + 'e' // returned word until now: 'eh'
third iteration: return reverse('lo') + 'l' // returned word until now: 'leh'
fourth iteration: return reverse('o') + 'l' // returned word until now: 'lleh'
fifth iteration: return reverse('') + 'o' // returned word until now: 'olleh'
sixth iteration: return '' // loop finished and returned word is 'olleh'

Hope this helps

Upvotes: 4

apsillers
apsillers

Reputation: 115950

A recursive function has two cases: a base case and a recursive case. Here, the base case is if (str === ""){ return ""; }, and the recursive case is return reverse(str.substr(1)) + str.charAt(0).

Consider the base case in action: reverse("") produces "". That's easy enough!

Now let's consider the second-most simple case: reverse("c"). This causes reverse(str.substr(1)) + str.charAt(0) to become reverse("") + "c", which we can easily see is just "c".

Next, reverse("bc"). In this case, the expression reverse(str.substr(1)) + str.charAt(0) becomes reverse("c") + "b". We know from above that reverse("c") is just "c". Thus, we see that reverse("c") + "b" is "cb".

Finally, let's graduate to understanding reverse("abc"). Here, the recursive case is reverse("bc") + "a". How can we figure out what reverse("bc") is? We jsut did! Relying on the explanation just given, we know that reverse("bc") is "cb", so reverse("bc") + "a" is "cba".

Upvotes: 1

Related Questions