Stringreversal with a recursive Method in Java doesnt work, but why?

Question

I wrote the program as a algorithm practice task. The method should get a String and convert it to a character array. And then swap the last character with the first and so on. But i am stumped and even though i might know the mistake, i dont know how to fix it.

This is the code:

package Rekursion;

public class StringReversal {

    char[] chars;
    int i = 0;
    int j;

    public String reversString(String text) {

        chars = text.toCharArray();
        j = chars.length-1;//Here i think is the mistake where j gets reset to array length and doesnt iterate properly but i need the length inside the method because of the parsed String


        if (i > j) {
            return String.valueOf(chars);
        }

        else {

            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;

            i++;
            j--;

            return reversString(String.valueOf(chars));
        }
    }

public static void main(String[] args) {
      StringReversal sr = new StringReversal();
        System.out.print(sr.reversString("gras"));
    }
}

And here is the console output: sgra

But the expected output is: sarg

I tried playing around with the condition but the condition should be fine. And i dont know how to fix even my commented mistake

Answer 1

Here is an alternate way to recursively reverse a string.

• No need to check for length of string. And I just let an NPE signal a null string as an argument.
• this works by continually passing the substring starting at 1 until only one character remains.
• the stack unwinds and builds the string in reverse.

public static String reverse(String str) {
    String result = "";
    if (str.length() > 0) {
        return reverse(str.substring(1)) + str.charAt(0);
    }
    return result;
}

The above does pollute the call stack with large substrings instead of individual characters but is ok for most applications. But using recursion in any fashion is not the best approach.

A better approach, imho, is to build the reversed string by swapping the end characters of a character array, iterating only halfway thru the string. This works whether the string is of even or odd length.

public static String reverse(String str) {
    char[] rev = str.toCharArray();
    for (int i = 0; i < rev.length / 2; i++) {
        char s = rev[i];
        char e = rev[rev.length - i - 1];
        rev[rev.length - 1 - i] = s;
        rev[i] = e;
    }
    return new String(rev);
}

Answer 2

You have indeed identified the problem correctly, the simple fix is to provide i and j as parameters to the method and pass the starting values (which is 0 and s.length()-1) while calling the reverseString method in main method. You can also improve the program by not converting the String to char array everytime. You can pass the character array as parameter once and while returning you can convert it back to String

public class StringReversal {

    public String reversString(char[] chars, int i, int j) { 

        if (i > j) {
            return new String(chars);
        }

        else {

            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;

            i++;
            j--;

            return reversString(chars,i,j);
        }
    }

    public static void main(String[] args) {
        StringReversal sr = new StringReversal();
        String s = "gras";
        System.out.print(m.reversString(sr.toCharArray(), 0, s.length()-1));
    }
}

Answer 3

This may seem simpler:

public static String reversString(String input) {
    if (input == null || input.length() < 2)
        return input;
    else
        return  input.substring(input.length() - 1) 
                + reversString(input.substring(1, input.length() - 1)) 
                + input.substring(0, 1);
}