0

I have to use recursion for this problem, I managed to make it work using loops pretty quickly but I'm a bit stuck on this. My current code is

public static String ReverseR(String n){
    String finalstring="";
    int i = 0;
    int len = n.length();
    while (i < len) {
        finalstring += (n.charAt(len -  1));
        ReverseR(n.substring(0, len - 1));
        i++;
    }
    return finalstring;
}

When I input any string, the resulting string is the correct length, but only uses the last letter. Ex: ReverseR("Hello") = ooooo Any ideas?

2

4 Answers 4

5

Recursion is kind of like proof by induction.

  1. Get rid of the while-loop
  2. If you're inverting a 0-character string, that's easy: just return ""
  3. if you're inverting a n-character string, invert [0..n-2] and prepend the last letter. Which you're already doing.
Sign up to request clarification or add additional context in comments.

1 Comment

also "remember that Strings in java aren't mutable, you need to return the modified string"
1

change n.charAt(len - 1)) to n.charAt(len - i))

you are always in the same place with len -1 ;)

[EDIT]

while (i < len){
    finalstring += (n.charAt(len - 1 - i));
    ReverseR(n.substring(0, len - 1 - i));
    i++;
}

this will fix your code, however you have to choose between while or ReverseR(...)

Duplicate question, check this Reversing a String with Recursion in Java

2 Comments

while this does solve the proble, it removes the need for the recursion :) (which may be required for the OPs homework).
This will throw a StringIndexOutOfBoundsException
0

Here is a full working solution

public static String reverse(final String s) {
    if (s == null) {
        throw new NullPointerException();
    }

    final int length = s.length();
    if (length <= 1) {
        return s;
    } else {
        // s = start + lastChar
        final String start = s.substring(0, length - 1); 
        final char lastChar = s.charAt(length - 1);
        return lastChar + reverse(start);
    }
}

Comments

0

Your recursive algorithm shouldn't require any loops, i.e. while and for loops. Any looping constructs can essentially be implemented through recursion without ever touching a loop. An example of basic recursive String reversal could be like this:

public static String reverseR(String n){
  if (n.length() <= 1) return n;
  return reverseR(n.substring(1))+n.charAt(0);
}

With this algorithm, you're basically saying: return "the reverse of every letter but the first"+"the first letter"

A good thing to help with writing recursive algorithms is making a lot of assumptions. Assume first that your reverse function works and then place it within itself wherever you want to reverse a portion of your string. Just remember to add a base case and you'll be golden. Languages like Haskell or Prolog will get you used to recursive algorithms since that is their main source of iteration.

2 Comments

Ah, good find. Looks like this is a pretty common way of doing this!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.