I am trying an example from my CS class. We learned recursion recently, and one of the examples I was given was to reverse a given string. The Java program compiles correctly, but when it is actually executed, instead of getting the intended result, I get this as my outcome.

at RevString.reverse(RevString.java:16)

This repeats itself until the program ends.

Here is the source code.

//demonstrate recursion by reversing a string of characters

public class RevString
	{
		public static void main(String[] args)
			{
				String s= "abcd";// the given string
				System.out.println(reverse(s));//shows the result of reversing the    string

			}
/*
//The reverse method takes a string variable as a parameter.
//It then takes the first character of a string and
//attaches it to the end of the string.
*/
				
		public static String reverse(String s)
			{
				if(s.length()==1)
					return s; //returns the original string only if it is one character
				
				else
					reverse(s.substring(1) + s.charAt(0));//calls the reverse method to take the first character and reverse it
					return s;
			}
	}

What am I doing wrong?

that's not the only thing it's telling you ;)

Anyway, why go to all that trouble to reverse a String when you can do it with a single line of code?
Sheesh, can't teachers ever come up with realistic assignments? ;)

Hi ,
You must have a condition to break the recursive call.
That is if that condition meets it should not call itself.

The problem is with the statement reverse(s.substring(1) + s.charAt(0)); . This effectively ends up passing the same string to the 'reverse()' function because of which it never breaks out. A proper way of doing it would be return(reverse(s.substring(1)) + s.charAt(0)); .

But as such this solution seems memory intensive since strings in java are immutable and you manipulate them for a greater part of the program. A slightly better and more OO way would be:

public class Recursion
{
    public static void main(String[] args)
    {
        Reverser r = new Reverser("123");
        System.out.println(r.reverse());
        r.setString("HellO");
        System.out.println(r.reverse());
    }
}

class Reverser
{
    char _arr[];

    int _pos;

    StringBuilder _buf;

    public Reverser(String str)
    {
        setString(str);
        init();
    }

    public String reverse()
    {
        init();
        return (doReverse().toString());
    }

    private StringBuilder doReverse()
    {
        int pos = _pos;
        if (pos == _arr.length - 1)
        {
            return (_buf.append(_arr[pos]));
        }
        else
        {
            ++_pos;
            return (doReverse().append(_arr[pos]));
        }
    }

    public void setString(String str)
    {
        _arr = str.toCharArray();
    }

    public String getString()
    {
        return (new String(_arr));
    }

    private void init()
    {
        _pos = 0;
        _buf = new StringBuilder(_arr.length);
    }
}
public String reverse(String str){
        if (str==null){
            return null;
        }
        int l=str.length();
        if (l==1){
            return str;
        }
        else if(l>1){
            return str.charAt(l-1)+reverse(str.substring(1,l-1))+str.charAt(0);
        }
        return str;
    }

Edited 3 Years Ago by mike_2000_17: Fixed formatting

And another variation where index is initially the length of the String:

public String reverse(String s, int index ){
   
    if( index >0 )
    {
     return s.charAt( --index) + reverse( s, index);
    }

    return "";
  }
This article has been dead for over six months. Start a new discussion instead.