CODEWITHSUNDEEP
javastringrecursionreverse
coinbird
coinbird

Reputation: 1217

Using recursion to reverse even indices of a String

For this part of my recursive method I need to handle the case of an even length string greater than 2 (as shown in my base cases). My issue is figuring out how to make my recursive case actually approach my base cases. I'm not sure if I did the reversing part correctly either, as I get a Stack Overflow error due to the base cases never being hit. Here's the method in question. (I will handle the odd Strings after my current 'if' statement. I have "return null;" there at the moment so I can test my even case without the odd.)

EDIT: Example input: ABCDEF Example output: EBCDAF

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 revEven(inString.substring(0, inString.length() - 1) + inString.charAt(inString.length() - 1));
         }
      return null;
   }

Upvotes: 1

Views: 991

Answers (1)

Andrey Taptunov
Andrey Taptunov

Reputation: 9495

The reason why you get StackOverflowError is that your string doesn't change between recursive calls. In the line where you call the function again you just recreate initial string.

"ABCD" = "ABC" (substring (0,3)) + "D" (charAt(3)) - the same string.

Hint. Don't try to change the string in recursive calls. Probably, it's better to represent your string as array of chars, change indices in recursive calls and then swap chars in place which are pointed by even indices.

I didn't check corner cases but the idea is below:

public static String runEven(String string) {
     char[] array =  runEvenImpl(string.toCharArray(), 0, string.length());
     return new String(array);
}

public static char[] revEvenImpl(char[] array, int head, int tail) {
      if (head == tail)
         return array;
      if (head % 2 == 0 && tail % 2 == 0)
      {
           swap(array, head, tail);
      }
      revEven(array, head+1, tail-1);
   }

Upvotes: 1

Related Questions