Write a Recursive Function That Reverses the Input String

Write a recursive function that reverses the input string

I'll instead explain the recursive algorithm itself. Take the example "input" which should produce "tupni". You can reverse the string recursively by

• If the string is empty or a single character, return it unchanged.
• Otherwise,
  
  
  1. Remove the first character.
  2. Reverse the remaining string.
  3. Add the first character above to the reversed string.
  4. Return the new string.

Recursive function that reverses substring within a string

A function to reverse the string can swap the elements at both ends of the range and decrease the range by one on both sides.

void reversing(string& s, int start, int end) {
    if (start >= end)
        return;
    swap(s[start], s[end]);
    reversing(s, start + 1, end - 1);
}

And then inside main():

// ...
cout << "This is how your words look now:\n";
reversing(s, start, end);
cout << s << endl;

How to reverse a string recursively

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"

Python reversing a string using recursion

def rreverse(s):
    if s == "":
        return s
    else:
        return rreverse(s[1:]) + s[0]

(Very few people do heavy recursive processing in Python, the language wasn't designed for it.)

Reversing a String with Recursion in Java

The function takes the first character of a String - str.charAt(0) - puts it at the end and then calls itself - reverse() - on the remainder - str.substring(1), adding these two things together to get its result - reverse(str.substring(1)) + str.charAt(0)

When the passed in String is one character or less and so there will be no remainder left - when str.length() <= 1) - it stops calling itself recursively and just returns the String passed in.

So it runs as follows:

reverse("Hello")
(reverse("ello")) + "H"
((reverse("llo")) + "e") + "H"
(((reverse("lo")) + "l") + "e") + "H"
((((reverse("o")) + "l") + "l") + "e") + "H"
(((("o") + "l") + "l") + "e") + "H"
"olleH"

---

Related Topics