Whats the Best Way to Recursively Reverse a String in Java

Whats the best way to recursively reverse a string in Java?

The best way is not to use recursion. These stuff are usually used to teach students the recursion concept, not actual best practices. So the way you're doing it is just fine. Just don't use recursion in Java for these kind of stuff in real world apps ;)

PS. Aside what I just said, I'd choose "" as the base case of my recursive function:

public String reverseString(String s){
    if (s.length() == 0) 
         return s;

    return reverseString(s.substring(1)) + s.charAt(0);
}

Reversing a String with Recursion in Java

The function takes the first character of a String - str.charAt(0) - puts it at the end and then calls itself - reverse() - on the remainder - str.substring(1), adding these two things together to get its result - reverse(str.substring(1)) + str.charAt(0)

When the passed in String is one character or less and so there will be no remainder left - when str.length() <= 1) - it stops calling itself recursively and just returns the String passed in.

So it runs as follows:

reverse("Hello")
(reverse("ello")) + "H"
((reverse("llo")) + "e") + "H"
(((reverse("lo")) + "l") + "e") + "H"
((((reverse("o")) + "l") + "l") + "e") + "H"
(((("o") + "l") + "l") + "e") + "H"
"olleH"

reverse string using recursion

The line does executes, how can you say it does not executes. I have added the syso statement, it does print, actually you are calling substring in a recursion, once the length becomes 1, it will execute.

public static String reverseString(String str) {
        String reverse = "";
        if (str.length() == 1) {
            System.out.println("hi");
            return str; // at one point this condition will be true, but value never returns
        } else {
            reverse += str.charAt(str.length() - 1) + reverseString(str.substring(0, str.length() - 1));
            return reverse;
        }
    }

    public static void main(String a[]) {
        System.out.println(reverseString("Test"));
    }

output

hi
tseT

Using Recursion to Reverse a String

Instead of using a Scanner, you can make use of an overload of String.split to split words around the first space:

public static String reverse(String words) {
    String[] wordArr = words.split(" ", 2); // split into a maximum of 2 Strings

    if (wordArr.length > 1) { // If there is more than 1 word
        // return the first word (wordArr[0]),
        // behind the reverse of the rest of the String (wordArr[1])
        return reverse(wordArr[1]) + " " + wordArr[0];
    }

    return wordArr[0]; // else, just return the one word
}

Reversing a String Using Recursion

Your method should take a String argument; using a static field might work but has a bad code smell. Anyway, take the last character in the input String and then substring everything else. Like,

public static String reverse(String str) {
    if (str.length() <= 1)
        return str;
    else
        return Character.toString(str.charAt(str.length() - 1))
                + reverse(str.substring(0, str.length() - 1));
}

If you must do it with the global, it could be done with something similar but you must update origChars before you call reverse() (without arguments) like

private static String origChars;
public static void reverse() {
    if (origChars.length() <= 1)
        System.out.print(origChars);
    else {
        System.out.print(origChars.charAt(origChars.length() - 1));
        origChars = origChars.substring(0, origChars.length() - 1);
        reverse();
    }
}

calling stack of reversing a string use recursion

Your program work fine But you unable trace your program. Below i show stack frame of all recursive call in your program(both stack up and stack down).

---

Related Topics