CODEWITHSUNDEEP
javarecursion
Vijay Nandwana
Vijay Nandwana

Reputation: 2634

reverse string using recursion

Could anyone please explain why "return str" line never executes?

public static String reverseString(String str){
    String reverse="";
    if(str.length() == 1){
        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"));
}

Upvotes: 0

Views: 734

Answers (5)

Levent Divilioglu
Levent Divilioglu

Reputation: 11602

Actually it hits and executes, check this out;

public static String reverseString(String str){
    String reverse="";
    if(str.length() == 1 ){
        System.out.println("HIT: " + str);  // CHECKING HIT
        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("Abcd"));
}

If you run this code, you will see the output as below;

HIT: A
dcbA

To Understand how this code is working, you have to understand how reverse method call itself and completes its process;

Check the image down below;

enter image description here

As you can see, on the 3rd step, because that the recursive function's input string length equals to 1, that part of the code is executed.

Hope that all these helps.

Upvotes: 0

Mehdi
Mehdi

Reputation: 3763

You can easily use StringBuilder#reverse method

public String reverser(String str){
   return new StringBuilder(str).reverse().toString();
}

Upvotes: 1

Peter Pan
Peter Pan

Reputation: 24138

My Implemention:

    public static String reverse(String str) {
        if(str.length() > 1) {
            return str.substring(str.length()-1)+reverse(str.substring(0, str.length()-1));
        } else {
            return str;
        }
    }

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

output:

tseT

Upvotes: 0

almightyGOSU
almightyGOSU

Reputation: 3739

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

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

Just add a print within your recursive function, to trace what is happening.

Output:

Current: T      // return str
Current: eT     // return reverse
Current: seT    // return reverse
tseT            // final return reverse

From the output, you can convince yourself whether str is being returned.

Upvotes: 0

Ankur Singhal
Ankur Singhal

Reputation: 26067

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

Upvotes: 2

Related Questions