Reversing strings using recursion

Question

I'm trying to solve exercises where I am required to use recursion. I wrote this:

static String reverse(String word){
    if(word.length()<2){
        return word;
    }
    else{
        int index = word.length() - 1;
        return word.charAt(index) + reverse(word.substring(0, index));
    }
}

But the answer for that question was the following code:

static String reverseRecursively(String str) {
    //base case to handle one char string and empty string
    if (str.length() < 2) {
        return str;
    }

    return reverseRecursively(str.substring(1)) + str.charAt(0);

}

And now let's suppose that you are a recruiter and got the first solution. Do you accept it? If not, why? What should I do better?

Answer 1

In production Java code, you would never reverse a string using recursion, primarily due to efficiency concerns, and also because new StringBuilder(str).reverse().toString() is better. Therefore, this question should be treated as an academic exercise — a quick test to weed out candidates who don't understand recursion at all. I don't think that an optimal solution is required.

Basically, your solution is good enough. That said…

• I prefer your reverse() to reverseRecursively(), since I consider the recursion to be an implementation detail that doesn't need to be reflected in the name.
• str is a more appropriate parameter name, since the function doesn't care whether the string is a word or not.
• The way you sliced the string is less elegant than in the second solution.
• I find your brace style slightly irksome. (Normally I wouldn't say anything about it, but given how little code I have been given to evaluate, I'm judging you on that.) Try to stick to the obsolete official Java style guide or Google's Java style guide, which is a close derivative of it.

Answer 2

Your code is definitely fine although it has a few minor issue. These issues are all fixed in the text book answer for the problem

The first issue is that the else statement is not needed. The method always returns inside the if statement if it reaches it. Omitting the else makes your code more concise.

The other issue is inside the else statement. It's unnecessarily complicated to move the last index to the front and much easier to move the first index to the back because the first index is always 0.

Finally, a minor detail I would change is the lack of access modifier for your method. Access modifiers help to show the intended scope of a method.

Answer 3

I'll accept both solutions. In fact, I think your own solution is arguably easier to read, if you drop the else and rename your temporary variable:

if (word.length() < 2) {
    return word;
}
int lastIndex = word.length() - 1;
return word.charAt(lastIndex) + reverse(word.substring(0, lastIndex));

That can be read as "get the character at lastIndex, and append the reverse of the word from the start to just before lastIndex". This literally chains my train of thought on lastIndex as the anchor point of doing the reversal. Given the left-to-right reading style for English, this 'shifting right' idea is intuitive.

Compare this with the suggest answer, which I will attempt to read as "get the reverse of the word from the second character onwards, and append the first character at the end". The idea of doing the reversal by 'shifting left' is not well-contained as a form of mental evaluation (for English).

If one is splitting hairs though, the suggested answer can be faster, but at this point we're really talking about micro-optimizations here (e.g. performing the reversal 10000 times on 1000-character Strings). It doesn't require the computation of word.length() - 1, and the implementation of String.substring(int) is slightly simpler compared to String.substring(int, int).

Unless there is a real performance concern for what you say are only recursion exercises, I'll say this is not something to be overly concerned about, and your own solution is good enough.