Skip to main content
CodePeet

Reverse a String Using Recursion

Try it yourself
EasyProblem

Description

Given a string s, return it reversed, with its characters in the opposite order, using recursion.

Examples

Example 1

Input: s = "hello"

Output: "olleh"

Explanation: The last character comes first: o, l, l, e, h.

Example 2

Input: s = "a"

Output: "a"

Explanation: One character is its own reverse.

Example 3

Input: s = "ab"

Output: "ba"

Explanation: Two characters swap places.

Example 4

Input: s = "racecar"

Output: "racecar"

Explanation: A palindrome reads the same both ways.

Constraints

  • 1 ≤ s.length ≤ 500
  • s consists of printable ASCII characters

Editorial

Approach - Reverse the Rest, Then Add the First

Intuition

The first character of s belongs at the end of the answer. Everything after it, reversed, comes before it. So reverse the rest with the same function, a string one shorter, and add the first character at the end. A string of 0 or 1 characters is its own reverse: that's the base case.

The adding happens after the call returns, so the characters land on the way back: the last call places the last character first.

Step-by-Step Explanation

Let's trace Example 1, s = "hello":

  1. reverse("hello") = reverse("ello") + h = "olleh".
  2. reverse("ello") = reverse("llo") + e = "olle".
  3. reverse("llo") = reverse("lo") + l = "oll".
  4. reverse("lo") = reverse("o") + l = "ol".
  5. reverse("o") is the base case: it returns "o".

Reverse the Rest — Each call hands on all but its first character, then adds it at the end once the rest comes back reversed.

Algorithm

  1. If s has at most one character, return it.
  2. Otherwise return reverse(s[1:]) followed by s[0].

Code

class Solution {
public:
    string reverseString(string& s) {
        if (s.size() <= 1) return s;        // nothing to turn around
        string rest = s.substr(1);
        return reverseString(rest) + s[0];
    }
};

class Solution:
    def reverseString(self, s: str) -> str:
        if len(s) <= 1:
            return s                        # nothing to turn around
        return self.reverseString(s[1:]) + s[0]

class Solution {
    public String reverseString(String s) {
        if (s.length() <= 1) return s;      // nothing to turn around
        return reverseString(s.substring(1)) + s.charAt(0);
    }
}

var reverseString = function(s) {
    if (s.length <= 1) return s;            // nothing to turn around
    return reverseString(s.slice(1)) + s[0];
};

Complexity Analysis

Time Complexity: O(n²)

In Python, Java and C++ each call copies the rest of the string, n - 1 characters, then n - 2, and so on. With at most 500 characters that's fine.

Space Complexity: O(n²)

n frames wait on the stack, each holding its own, shorter copy.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Putting the first character back in front. return s[0] + self.reverseString(s[1:])

On s = "hello" it returns "hello"; the answer is "olleh". The first character belongs at the end of the reversed string. s[0] + reverse(s[1:]) keeps it in front, and the same happens one level down, so the string comes back unchanged.

Returning nothing at the base case. return ""

On s = "hello" it returns "lleh"; the answer is "olleh". A string of one character is its own reverse, so the base case returns it. Returning "" loses the last character of every answer.

Mixing up which character is removed. return s[-1] + self.reverseString(s[1:])

On s = "abc" it returns "ccc"; the answer is "cba". Each call has to remove the same character it places. s[-1] + reverse(s[1:]) places the last character but hands on everything after the first, so the last one is used twice and the first one is lost.

Where This Pattern Is Taught

This problem practises doing the work after the call, on the way back. It's taught in Introduction to Recursion.