reverse string recursive method

Question

Hello Why my reverse method that uses recursion isn't working? The print statement shows that the operation is done correctly but at the end it seems like only the very ast char of the entire String is assigned to h.

    public static String reverse(String s,String h){

    if(s.length()==0){

        return s;

    } else {


        h+=s.charAt(s.length()-1);
        System.out.println(h);//FOR TEST
        s=s.substring(0,s.length()-1);
        reverse(s,h);
        return h;
    }

}

Any advice?

Chandu · Accepted Answer · 2011-06-06 05:50:27Z

5

Use

 return reverse(s,h);

instead of return h;

i.e:

public static String reverse(String s,String h){

    if(s.length() == 0){

        return h;

    } else {


        h+=s.charAt(s.length()-1);
        System.out.println(h);//FOR TEST
        s=s.substring(0,s.length()-1);
        return reverse(s,h); //NOTICE THE CHANGE HERE,
    }

}

edited Jun 6, 2011 at 5:50

answered Jun 6, 2011 at 5:30

Chandu

83.2k19 gold badges136 silver badges136 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

trutheality Over a year ago

Not quite: this returns an empty string.

JBoy Over a year ago

@ trutheality s will be empty but h will be s converted so thats what will be returned as s will be empty thank you Cybernate, but i still dont get why returning h wont work as in my code

Chandu Over a year ago

@JBoy: In your code you are not using/re-assigning the value returned by the recursive call made to reverse(s,h) right before calling return h and hence your code will always return the value assigned to h in first iteration.

luqui · Accepted Answer · 2011-06-06 05:32:31Z

4

Strings in Java are immutable. So in this code:

private static void foo(String x) {
    x += "bar";
}

public static void main() {
    String a = "foo";
    foo(a);
    System.out.println(a);
}

Only "foo" will be printed. It works the same way as if the type were int.

So your reverse function needs to do something with the return value. When you call reverse(s,h) you are throwing away the return value from the recursive call. You need to incorporate it:

String rec = reverse(s,h);
return ... something involving rec ...;

answered Jun 6, 2011 at 5:32

luqui

60.7k12 gold badges153 silver badges210 bronze badges

Comments

trutheality · Accepted Answer · 2011-06-06 05:50:19Z

1

2 things:

public static String reverse(String s,String h){

    if(s.length()==0){

        return h; /// This needs to return the reversed string (h).

    } else {


        h+=s.charAt(s.length()-1);
        System.out.println(h);//FOR TEST
        s=s.substring(0,s.length()-1);
        h = reverse(s,h);   /// You need to use the return value
        return h;
    }

}

It looks like you were trying to change h using a return-by-reference-parameter. You have to remember that in Java everything (including references to objects) is passed by value. Once you write s=s.substring(0,s.length()-1);, s becomes a reference to a different String object, and that change is not propagated to the calling function.

Also, there is a way to implement this with only one input parameter.

edited Jun 6, 2011 at 5:50

answered Jun 6, 2011 at 5:37

trutheality

23.5k6 gold badges58 silver badges68 bronze badges

Comments

m3hr24d · Accepted Answer · 2012-08-22 23:26:32Z

I think this way is better for reversing a string using a recursive method :

public class Reversestringbyrecursivefunction {

    public static void main(String[] args) 
    {
        Scanner input=new Scanner(System.in);
        while(true)
        {
            System.out.print("[?] Enter String('q' for exit)> ");
            String str=input.next();
            if(str.equals("q"))
                break;
            System.out.println("this string created by reversed recursive function : "+revers(str));
            System.out.print("\n==========================\n");
        }
        System.out.print("\n\n\t\t\t[ GOOD LUCK!!! ]\n");
    }
    static String revers(String str)
    {
        if(str.length()<=1)
            return str;
        else
            return revers(str.substring(str.length()-1, str.length()))+revers(str.substring(0, str.length()-1));
    }
}

but , for best performance you should change this line :

return revers(str.substring(str.length()-1, str.length()))+revers(str.substring(0, str.length()-1));

to :

return str.substring(str.length()-1)+revers(str.substring(1, str.length()-1)+str.substring(0,1);

in prior line: in best performance and in one stage you can swap only 1 character of input string . but , in new line: in one stage you can swap 2 character of input string

Collectives™ on Stack Overflow

reverse string recursive method

4 Answers 4

3 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related