Trying to reverse a string using recursion

user_9314490 0
Viewed 51

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;
        
    }
}
recursion algorithm java string
1 Answers

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.

user_18632290
Related