Trying to reverse a string using recursion

Question

I've having trouble reversing a string using recursion - I'm pretty new at this concept.

I'm testing my code with the word "hello". It is only printing out 'h' at the end and not the entire string I was trying to build up during the recursion. I know using strings to add is slow but I haven't thought about making it faster right now since it is not working.

public class MyClass 
{
    public static void main(String[] args) {
        System.out.println(reversedString("hello", 0, ""));
    }
    
    public static String reversedString(String str, int index, String sb) {
        
        if(index == str.length()) {
            return null;
        }
       
        reversedString(str, index + 1, sb);
        sb = sb + str.charAt(index);
        return sb;
        
    }
}

Thanks, I've looked over that - I'm more confused about what's wrong with my specific implementation - in my mind it should work but it doesn't. — CISSflow, Oct 16 '20 at 06:44

score 0 · Answer 1 · answered Oct 16 '20 at 06:47

Here is a working slight modification of what you posted above:

public static String reversedString(String str, int index, String sb) {
    if (index == str.length()) {
        return "";
    }

    sb = reversedString(str, index + 1, sb) + str.charAt(index);

    return sb;  
}

System.out.println(reversedString("hello", 0, "")); // prints olleh

The logic here is that we concatenate the reversed string together by putting the result from the recursion first, followed by the single character at each level of the recursion. Concatenating in this order is critical, because we want to reverse the string, which means conceptually that the later characters need to appear first.

The base case occurs when we have run out of more characters to process. In this case, we just return empty string.

Trying to reverse a string using recursion

1 Answers1