Recursive string reversal function in javascript?

Question

I'm a pretty experienced frontend engineer with a weak CS background. I'm trying to get my head around the concept of recursion. Most of the examples and purported explanations I can find just aren't explaining it in a way I find easy to understand.

I set myself a task of writing a function that will reverse a string recursively. I know there has to be a base condition (i.e. the solution is found), but I can't figure out how to actually write something like this and could use a demo to study.

Could someone provide a sample function?

Answer 1

Something like:

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

So the function is recursive as it calls itself to do the work.

Answer 2

A tail recursive version, just for kicks (even though JavaScript doesn't perform tail call elimination):

function reverse(str) {
  function r(s, acc) {
    return (s.length == 0) ? acc : r(s.substr(1), s.charAt(0) + acc);
  };
  return r(str, '');
};

Answer 3

One line of code using boolean operators.

Explanation: if string exists call the recursion to reduce the string, otherwise fallback to non existing string (last recursive call)

  function reverseString(s) {
    return s && reverseString(s.slice(1)) + s[0] || s;
  }

Answer 4

A 25% faster function: jsperf.com

function Reverse(str) {
  if (str === null) {
    return null;
  }
  if (str.length <= 1) {
    return str;
  }
  var first = str[0];
  var last = str[str.length - 1];
  var str1 = Reverse(str.substring(1, str.length - 1));
  return last + str1 + first;
}

var result = Reverse("a really serious string of nothingness making call stack to explode");

Answer 5

function reverse(str) {
  if(str.charAt(0) === ''){
    return "";
  }
  return str.charAt(str.length -1) + reverse(str.substring(0,str.length-1));
}

Answer 6

//call this function with the string as parameter

function strrev(str) {
    return str.length !== 1 ? strrev(str.slice(1))+str[0] : str;
}

Answer 7

According to the MDN Web Docs, you should use substring() instead of substr():

Warning: Although String.prototype.substr(…) is not strictly deprecated (as in "removed from the Web standards"), it is considered a legacy function and should be avoided when possible. It is not part of the core JavaScript language and may be removed in the future. If at all possible, use the substring() method instead.

Additionally, if no index is provided as a parameter to charAt(), the default is 0.

Therefore, we can write a recursive one-liner to reverse a string using a ternary operator and by applying the logic described above:

const reverse_string = s => s === '' ? '' : reverse_string(s.substring(1)) + s.charAt();

console.log(reverse_string('Hello, world!')); // !dlrow ,olleH

Answer 8

The base case that I am using for exiting the recursion is when the the length decrease to 0

On each recursive call we will take out the last character of the string and append it with the result that we will get from recursive call of a string, which is smaller in size as the last character is removed using slice.

function reverse(str){
 if(str.length===0)
    return "";

return str[str.length-1]+reverse(str.slice(0,str.length-1));
}

Answer 9

You can also use this code below for simple reversal of strings through recursion

const reverseIt = (x) => {
    if (x === "") {
      return "";
    }
    return x[x.length - 1] + reverseIt(x.substring(0, x.length - 1));
};

Answer 10

Here is how I solved it:

function reverse(s) {
  const index = s.indexOf(" "); 
  if(index === -1) {
    return s
  }
  else { 
      return reverse(s.slice(index+1)) + " " + s.slice(0,index)
  }
} 

Answer 11

Another solution:

function reverse(str, newStr = "") {
  // Base case
  if (str.length === 0) return newStr;
  // newStr += str.slice(-1)
  return reverse(str.slice(0, -1), newStr += str.slice(-1));
  }
  
  console.log(reverse("house")) // esuoh

Answer 12

Another solution using default parameters:

function reverse(str, newStr = "") {
  // Base case
  if (str.length === 0) return newStr;
  
  return reverse(str.slice(0, -1), newStr += str.slice(-1));
  }
  
  console.log(reverse("house")) // esuoh

Answer 13

So far the best I think:

function reverse(s) {
    if (s.length===1) return s;
    return reverse(s.slice(1)) + s[0];
}

Answer 14

Try this:

function recurse(s) {  
  if (s.length == 0) {  
    return '' // stopping condition  
  } else {  // return last char + result of function called with chars up to last char  
    return s.substring(s.length, s.length -1) + recurse(s.substring(0, s.length -1))  
  }
}  

Answer 15

It is verbose, but I like making it easy to understand in logical steps:

function rev(soFar, count){
   console.log("asString: " + soFar );
   console.log("count: " + count);
   var len = soFar.length;
   var ret = soFar;//ret needs to be a reference to soFar
   if(len > count){
      var subd = soFar.substring(1,len);
      var first = soFar[0];
      //we want to inject the first letter at the index position one back from the length, minus what the count is at this point
      var indexOfInsert = len-1 - count;//so if count is 0 and length is 5, we want 4 (4 -0)
      var asArray = subd.split("");
      asArray.splice(indexOfInsert,0,first);
      count++;//need to increment count for the next round
      var asString = "";
    //recreate as string, not array - the default toString() makes this a comma delimited string. It is best toi just recreate it in a loop
    for(var i = 0; i<len; i++){
        asString+=asArray[i];
    }
    ret = rev(asString,count);//ret always needs to be reassigned
}
//only get here when count is greater than the length of the original string
return ret;//will always be a reference to soFar, which is being reassigned in the recursive loop

}

Then call it like:

var reversed = rev("Hello",0);
console.log("result",reversed);

Answer 16

This is a pretty straightforward C# implementation of the algorithm you asked for. I think it could be rewritten in javascript pretty easily.

/*
C#: The Complete Reference 
by Herbert Schildt 

Publisher: Osborne/McGraw-Hill (March 8, 2002)
ISBN: 0072134852
*/


// Display a string in reverse by using recursion. 

using System; 

class RevStr { 

  // Display a string backwards. 
  public void displayRev(string str) { 
    if(str.Length > 0)  
      displayRev(str.Substring(1, str.Length-1)); 
    else  
      return; 

    Console.Write(str[0]); 
  } 
} 

public class RevStrDemo { 
  public static void Main() {   
    string s = "this is a test"; 
    RevStr rsOb = new RevStr(); 

    Console.WriteLine("Original string: " + s); 

    Console.Write("Reversed string: "); 
    rsOb.displayRev(s); 

    Console.WriteLine(); 
  } 
}