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?

Tom · Accepted Answer · 2011-02-01 05:29:18Z

36

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.

answered Feb 1, 2011 at 5:29

Tom

45.1k4 gold badges44 silver badges61 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

maerics Over a year ago

As straightforward as it gets.

Geuis Over a year ago

Thanks. This is really easy for me to understand. I'm next trying to see if I can manually reverse an array recursively.

maerics Over a year ago

The array version will be much trickier because arrays in ECMAScript (of which JavaScript is an implementation) are purely imperative...

Geuis Over a year ago

This is what I did for reversing an array: var x = function(arr){ if( arr.length === 1 ){ return arr; }else{ return x( arr.slice(1) ).concat(arr[0]); } } console.log( x([1,2,3,4]) );

Tim Down Over a year ago

slice() is preferrable to substr(): it's standardized in the ECMAScript spec and works uniformly cross-browser.

|

maerics · Accepted Answer · 2014-12-10 15:09:14Z

4

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, '');
};

edited Dec 10, 2014 at 15:09

answered Feb 1, 2011 at 5:34

maerics

157k47 gold badges277 silver badges299 bronze badges

3 Comments

KooiInc Over a year ago

what do you mean with even though JavaScript doesn't optimize?

maerics Over a year ago

Many compilers/interpreters perform tail call elimination (some language specs even require it) which makes tail-recursive functions perform comparably to their iterative counterparts. The ECMAScript specification has no such requirement and no existing JavaScript interpreters do it, as far as I know.

steviesh Over a year ago

in ES6 spec, tail calls are properly interpreted now.

EugenSunic · Accepted Answer · 2022-07-20 21:20:35Z

1

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;
  }

edited Jul 20, 2022 at 21:20

answered May 7, 2017 at 18:10

EugenSunic

13.8k15 gold badges68 silver badges96 bronze badges

Comments

Dima Daron · Accepted Answer · 2017-11-14 22:20:45Z

0

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");

answered Nov 14, 2017 at 22:20

Dima Daron

5781 gold badge8 silver badges21 bronze badges

Comments

Rahul Kishan · Accepted Answer · 2018-03-30 19:41:32Z

0

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

edited Mar 30, 2018 at 19:41

answered Mar 30, 2018 at 19:22

Rahul Kishan

3144 silver badges18 bronze badges

Comments

shantanu kaushik · Accepted Answer · 2018-07-27 13:11:27Z

0

//call this function with the string as parameter

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

answered Jul 27, 2018 at 13:11

shantanu kaushik

1141 silver badge5 bronze badges

Comments

Grant Miller · Accepted Answer · 2018-11-22 23:33:52Z

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

HarsimranJS · Accepted Answer · 2019-11-03 10:57:42Z

0

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));
}

answered Nov 3, 2019 at 10:57

HarsimranJS

215 bronze badges

Comments

Mehdi Raza · Accepted Answer · 2021-09-15 06:41:24Z

0

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));
};

answered Sep 15, 2021 at 6:41

Mehdi Raza

3854 silver badges16 bronze badges

Comments

hasn · Accepted Answer · 2021-10-21 08:27:20Z

0

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)
  }
}

answered Oct 21, 2021 at 8:27

hasn

8077 silver badges22 bronze badges

Comments

ark1980 · Accepted Answer · 2022-11-13 18:17:11Z

0

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

answered Nov 13, 2022 at 18:17

ark1980

3051 gold badge4 silver badges8 bronze badges

Comments

ark1980 · Accepted Answer · 2022-11-13 18:18:45Z

0

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

answered Nov 13, 2022 at 18:18

ark1980

3051 gold badge4 silver badges8 bronze badges

Comments

sangram · Accepted Answer · 2024-03-28 12:58:54Z

0

let fruit = "APPLE";

function reverseStringByRecursion(name) {
  if (name.length == 0) {
    return "";
  } else {
    let lastChar = name[name.length - 1];
    let excludingLastChar = name.slice(0, name.length - 1);
    return lastChar + reverse(excludingLastChar);
  }
}

var reversedString = reverseStringByRecursion(fruit);
console.log("Reversed string:", reversedString);

answered Mar 28, 2024 at 12:58

sangram

4355 silver badges6 bronze badges

Comments

qweszxcj · Accepted Answer · 2016-04-19 06:32:24Z

-1

So far the best I think:

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

edited Apr 19, 2016 at 6:32

answered Nov 19, 2015 at 6:28

qweszxcj

1538 bronze badges

Comments

Gerrat · Accepted Answer · 2017-05-26 21:48:17Z

-1

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))  
  }
}

edited May 26, 2017 at 21:48

answered Feb 1, 2011 at 5:31

Gerrat

29.9k9 gold badges78 silver badges104 bronze badges

Comments

Madness · Accepted Answer · 2015-08-27 20:45:17Z

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);

Development 4.0 · Accepted Answer · 2011-02-01 05:25:02Z

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(); 
  } 
}

Collectives™ on Stack Overflow

Recursive string reversal function in javascript?

17 Answers 17

9 Comments

3 Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

17 Answers 17

9 Comments

3 Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related