Reverse a string not using the substring method

[kathyla18]

hi , i need to implement a method that reverses a string but i can only use the method length, concant and charAt. I know how to do it with for loops or with the substring method , but im supposed to do it with recursion and im not allow to use the substring method.
Any help will be appreciated.

[Fubarable]

First thoughts:
A) what will the method return?
B) what will be the parameter passed to the method?

Edit: I don't know if this is the simplest way to do it, but here is a method signature that worked for me:

public static String reverseString(String input, String output, int index) { //...

[kathyla18]

i have to use the method
public String reverse(String string) and i can use helper methods

[emceenugget]

just use fubarable's method (or some variation of it) as a helper.

public String reverse(String string) {
   String retval = "";
   return reverseString(string, retval, 0);
}

or something like that.

[rdtindsm]

conceptually:
string reverse(string){
if string contains 1 character
return string
else
return cancatonate(reverse(restof string), first element in string)
end reverse

My intro to programming used scheme (LISP variant), and we were about 6 weeks into the course before we stopped using strictly recursive techniques. My infinite all but dissappeared.

[Fubarable]

not bad, but "restof string" will need subString which the OP states cannot be used.

[Eranga]

On a loop, get each character from the last index and append it into an empty string.

[faisalcmpm]

private String reverse(String string) {
		String returnString =null;
		if(string.length() == 1) {
			returnString =  string;
		} else {
			returnString = String.valueOf((string.charAt(string.length() -1)));
			returnString = returnString.concat(reverse(String.valueOf(string.subSequence(0, string.length() -1))));
		}
		return returnString;
	}

[mtyoung]

subSequence...
substring... , i think they functions the same... do not can use in the code or not

Eranga said

On a loop, get each character from the last index and append it into an empty string.

that recursive function may intake 2 parameters, String and int
int can indicate the starting pos(increment from 0 to length - 1) or ending pos (decrease from length - 1 to 0)
return char or string with 1 length, or what ever you like

[Eranga]

Something like this.

private String getReversString(String str) {
String temp = "";
for(int i = 0; i < str.length(); i++) {
try {
temp = str.charAt(i) + temp;
}
catch(IndexOutOfBoundsException ex) {
System.out.println("Index out of range exception found");
}
}
return temp;
}

Ordering characters in reverse order. ;)

[faisalcmpm]

This is correct.
But his assignment is to bring up this without using
1 for loop
2 substring
and the method should be recursively called

[Eranga]

On the original post only talking about the substring()

[Fubarable]

something like so:

public static String reverseString(String input, String output, int index)
{
  if (index == 0)
  {
    return output;
  }
  else
  {
    output += input.charAt(index - 1);
    return reverseString(input, output, index - 1);
  }

called with

String input = "Hello world!";
String reverseString = reverseString(input, "", input.length());

code not tested

[rdtindsm]

The original post did call for recursion, and was later clarified with a specific function signature.

emceenugget's method is IMHO, the best and correct method to solve the problem by adding a wrapper to call fubarable's method.

Pedagogical insights:
The use of helper methods.
That a recursive formulation of a problem can give easily understood insights regarding the solution, even if loops are a better (less memory, limited stack frame) solution in the long term. (just reverse the rest of the list and add the head to the end).

Let me also point out that passing the original string and an index is defining the "rest of the string", i.e., everything beyond the index. A substring method will work, so will passing an index (pointer) into the string.

I don't know how substring actually works, but a string variable is usually a pointer, and substring could be implemented by simply returning the pointer to the position in an existing string, rather than creating a new string. That is, passing a string and a pointer (index) is a simple implementation of substring. This would particularly be true in C. i.e. substring = string + ndx with its null terminated strings.

Don't want to be defensive, and I am, about any criticism of my previous post. fubarable understandably assumed an implementation I didn't state. Part of the scenery of forums, but I also think it is instructive to consider how these things work under the hood. Probably part of the point of the exercise.

Would be an interesting experiment which I may do later. If I declare String str = new String("abcdef") (and forgive any syntax errors) what is the value of foo = substring(ndx,str). Is the value of foo reasonably close to str , or way off in a distant area of the heap? Does foo increment in a constant way for substring(ndx + 1), str)?

So, my mind is racing trying to figure out the exact testing code, but, as I loved to see, that will be left as an exercise for the student.

[kathyla18]

i tested your code (Fubarable) and it works, but im supposed to use reverse(string) to call the method, and not
reverseString(input, "", input.length());

[Fubarable]

Don't want to be defensive, and I am, about any criticism of my previous post. fubarable understandably assumed an implementation I didn't state. Part of the scenery of forums, but I also think it is instructive to consider how these things work under the hood. Probably part of the point of the exercise.

Sorry about making assumptions about code not posted. You are correct, and I have nothing really to add to your previous well-written post.

[emceenugget]

once again, just encase fubarable's method within one that fits your requirements.

[Eranga]

i tested your code (Fubarable) and it works, but im supposed to use reverse(string) to call the method, and not
reverseString(input, "", input.length());

So the length validation of the original string and the temporary string object to store the return string declarations do inside the reverseString method.