Stack overflow error in a recursive method

Question

My method is supposed to reverse the even indices of a given String.

EDITED WITH UPDATED CODE:

public static String revEven(String inString)
{
  String tempString = new String();

  if (inString.length() <= 2)
     return inString;
  if (inString.length() == 3)
  {
     tempString += inString.charAt(2);  
     tempString += inString.charAt(1);
     tempString += inString.charAt(0);

     return tempString;
  }
  if (inString.length() % 2 == 0)
  {
     return tempString += 
            revEven(inString.substring(0, inString.length() - 1)) +
            inString.charAt(inString.length() - 1);
  }
  else
  {
     return tempString += 
            inString.charAt(inString.length() - 1) + 
            inString.charAt(1) +
            revEven(inString.substring(2, inString.length() - 2)) +
            inString.charAt(inString.length() - 2) +
            inString.charAt(0);
  }
}

I ran through the recursion on paper, and it should be working correctly. When I enter abcde for a test I get 199cda printed out. It should print out ebcda.

It seems like it's printing out memory addresses or something, but I can't seem to figure out why.

Taylor Hx · Accepted Answer · 2014-03-05 05:49:38Z

2

Your edited code is returning exactly what it should.

The code below:

return tempString += 
        inString.charAt(inString.length() - 1) + 
        inString.charAt(1) +
        revEven(inString.substring(2, inString.length() - 2)) +
        inString.charAt(inString.length() - 2) +
        inString.charAt(0);

treats the first + as the addition operator, not the concatenation operator, adding the last char to the second char of the String. In Java, char values can be added together to produce numbers (in Java, 'a'+1 = 98, the numeric value of the char b).

The code below fixed the problem by concatenating to an empty string, therefore letting the Java compiler know that everything that follows is concatenation, not addition.

return tempString += "" 
    + inString.charAt(inString.length() - 1)
    + inString.charAt(1)
    + revEven2(inString.substring(2, inString.length() - 2))
    + inString.charAt(inString.length() - 2)
    + inString.charAt(0);
}

answered Mar 5, 2014 at 5:49

Taylor Hx

2,84325 silver badges36 bronze badges

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

3 Comments

Commander Coriander Salamander Over a year ago

Props - I had gotten to the point where I'd figured out that doing += for every one made it work properly, but I don't know Java well enough to figure out why ^^

Taylor Hx Over a year ago

@CommanderCorianderSalamander That's the downside to having an overloaded operator such as + I guess, makes debugging unusual cases like this a little more difficult. It's times like these one sees the value of StringBuilder.

coinbird Over a year ago

Wow! I did not know it worked like that. I added the "" and sure enough, it did String concatenation instead. Thank you very much for all your help!

Taylor Hx · Accepted Answer · 2014-03-05 04:48:27Z

1

Best way to accomplish this is to have two method calls: one for your initial step (getting only the characters at even indices) and your recursive step (reversing a String).

The first step should look something like below:

public static String reverseEven(final String inString) {
    String tempString = "";
    for(int i = 0; i < inString.length(); i=i+2) {
        tempString += inString.charAt(i);
    }
    return revEven(tempString);
}

The above code takes only every second character from the original String and passes it your method.

The code you have so far almost performs this second step, bar a StackOverflowException.

To fix this, change the line:

return tempString += revEven(inString.substring(0, inString.length() - 1) + inString.charAt(inString.length() - 1));

to:

return tempString += inString.charAt(inString.length() - 1) + revEven(inString.substring(0, inString.length() - 1));

Your original code threw a StackOverflowException on Strings with an even number of characters since it would always the entirety of inString, because you would always add the last character (the one your substring call removes) back on to the end, resulting the in the same String over and over.

The suggested fix, instead, add this last character to the start of the String and reverses the rest as if it had an odd number of characters.

answered Mar 5, 2014 at 4:48

Taylor Hx

2,84325 silver badges36 bronze badges

2 Comments

coinbird Over a year ago

Thanks for the info. I'm not getting the error anymore thanks to passing only part of the String into the method, and eventually hitting the base case. It is, however, returning what seems to be a memory address. I posted my updated code above.

Taylor Hx Over a year ago

@CoinBird Ahh, I see. I've posted a new answer, as your revised code is essentially a new question. See it here.

Commander Coriander Salamander · Accepted Answer · 2014-03-05 04:16:48Z

0

The problem is that you split the string from the start to one away from the end, but then add on the last character before you call the function, so you effectively call it with the same string over and over and over.

When you call inString.substring(0, inString.length() - 1) on the string "Hello", for example, length() returns 5 - so that is the substring from indices 0 to 4, not including 4. That's all well and good, but then you add the character at index 4 on - or the last character.

Change the call revEven(inString.substring(0, inString.length() - 1) + inString.charAt(inString.length() - 1)) to just revEven(inString.substring(0, inString.length() - 1)).

answered Mar 5, 2014 at 4:16

Commander Coriander Salamander

6201 gold badge5 silver badges10 bronze badges

2 Comments

Taylor Hx Over a year ago

The original poster is trying to reverse only the character at even indices, not the entire String.

coinbird Over a year ago

Ahh, I had too many parenthesis so the entire thing was being passed back through. Thanks.

Collectives™ on Stack Overflow

Stack overflow error in a recursive method

3 Answers 3

3 Comments

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related