javascript - How to reverse a string recursively - Stack Overflow

admin管理员组

文章数量:1410725

I was in an interview the other day and I was asked to write a method that reverses a string recursively.

I started writing a method that calls itself and got stuck.

Here is what I was asked, reverse a string "Obama" recursively in JavaScript.

Here is how far I got.

function reverseString(strToReverse)
{

         reverseString(strToReverse);

};

And got stuck, they said NO for i loops.

Anyone got any ideas?

I was in an interview the other day and I was asked to write a method that reverses a string recursively.

I started writing a method that calls itself and got stuck.

Here is what I was asked, reverse a string "Obama" recursively in JavaScript.

Here is how far I got.

function reverseString(strToReverse)
{

         reverseString(strToReverse);

};

And got stuck, they said NO for i loops.

Anyone got any ideas?

• javascript
• recursion

Share Improve this question Follow asked May 21, 2015 at 19:43 Filling The Stack is What I DOFilling The Stack is What I DO 6,7411515 gold badges5757 silver badges8888 bronze badges 10

• Why does it need to be called recursively? 'Obama'.split('').reverse().join('') isn't enough? – danronmoon Commented May 21, 2015 at 19:45
• 3 @danronmoon It says it was for an interview. – loganfsmyth Commented May 21, 2015 at 19:46
• 1 possible duplicate of How do you reverse a string in place in JavaScript? – Kevin Ji Commented May 21, 2015 at 19:47
• 3 There is an answer, but I'm not sure we are here for you to help you get through the interview. This is something you need to do for yourself. – Mr Lister Commented May 21, 2015 at 19:48
• 1 @AlumCloud.Com The reason why they ask for a recursive function (even if there is a better way to solve it) is because they want to see how you think and see if you can logic your way out of it – Daemedeor Commented May 21, 2015 at 19:52

 |  Show 5 more ments

9 Answers 9

Sorted by: Reset to default 5

Look at it this way: the reversed string will start with the last letter of the original, followed by all but the last letter, reversed.

So:

function reverseString(strToReverse)
{
  if (strToReverse.length <= 1)
    return strToReverse;

  // last char +
  // 0 .. second-last-char, reversed
  return strToReverse[strToReverse.length - 1] + 
    reverseString( strToReverse.substring(0, strToReverse.length - 1) );
}

The simplest one:

function reverse(input) {
  if (input == null || input.length < 2) return input;
  return reverse(input.substring(1)) + input.charAt(0);
}

console.log(reverse('Barack Obama'));

See the solution by @MaxZoom below for a more concise version.

Note that the tail-recursive style in my own answer provides no advantage over the plain-recursive version since JS interpreters are not required to perform tail call elimination.

[Original]

Here's a tail recursive version that works by removing a character from the front of the input string and prepending it to the front of the "accumulator" string:

function reverse(s, acc) {
  if (s.length <= 0) { return acc; }
  return reverse(s.slice(1), s.charAt(0) + (acc||''));
}

reverse('foobar'); // => "raboof"

Single line solution. And if they asked I tell them it's recursive in the native code part and not to ask any more stupid questions.

var result = "Obama".split('').reverse().join('');

Output: amabO

The real problem here is not "how to reverse a string". The real problem is, "do you understand recursion". That is what the interview question is about!

So, in order to solve the problem, you need to show you know what recursion is about, not that you can reverse the string "Obama". If all you needed to do was reverse the string "Obama", you could write return "amabO"; see?

In other words, this specific programming task is not what it's all about! The real solution is not to copy and paste the code from the answers here, but to know about recursion.

In brief,

• Recursion involves calling the same function again, yes, but that's not all
• In order to prevent stack overflow, you MUST ensure that the function doesn't call itself indefinitely
• So there's always a condition under which the function can exit without calling itself (again)
• And when it does call itself again, it should do so with parameters that make the above condition more likely.

In the case of string operations, one way to make that all happen is to make sure that it calls itself only with strings that are shorter than the one it was called with. Since strings are not of an infinite length, the function can't call itself an infinite number of times that way. So the condition can be that the string has a length of zero, in which case it's impossible to call itself with a shorter string.

If you can prove that you know all this, and can use it in a real world program, then you're on your way to passing the interview. Not if you copy and paste some source you found on the internet.

Hope this helps!

We can easily reverse a string in the recursion method using the ternary operator

function reverseString(strToReverse) {

    return str.length > 1 ? reverse(str.slice(1)) + str.charAt(0) : str;
}

reverseString("America");

Not the smartest way to reverse a string, but it is recursive:

function reverse(input, output) {
    output = output || '';
    if (input.length > 0) {
        output = output.concat(input[input.length -1]);
        return reverse(input.substr(0, input.length - 1), output);
    }
    return output;
}

console.log(reverse('Obama'));

Here's a jsfiddle

Maybe something like this?

var base = 'Obama',
    index = base.length,
    result = '';

function recursive(){
    if (index == 0) return;
    index -= 1;
    result += base[index];
    recursive();
}

recursive();

alert(result);

jsfiddle: https://jsfiddle/hy1d84jL/

EDIT: You can think of recursion as an infinite for..loop. Let's just use it in "controlled" way and define the bounds - 0 for minimum and the length of Obama word as the maximum. Now, let's just make it call itself whatever number of times and do what you need in order to reverse the string, which is - decrement the index variable by one and sum the character from the end. Hope it helps. Nice question.

If the function can only have the single input i would split the string into smaller and smaller pieces, and add them all together in the reverse order

function reverseString(strToReverse){
  if (strToReverse.length <= 1) { return strToReverse; }

  return reverseString(strToReverse.substr(1, strToReverse.length - 1) + strToReverse[0];
}

本文标签： javascriptHow to reverse a string recursivelyStack Overflow