CODEWITHSUNDEEP
javarecursion
Howcan
Howcan

Reputation: 313

JAVA: help fixing recursive function

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?

Upvotes: 0

Views: 174

Answers (4)

user2466999
user2466999

Reputation: 107

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.

Upvotes: 0

X-Pippes
X-Pippes

Reputation: 1170

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

Upvotes: 1

Vertex
Vertex

Reputation: 2712

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);
    }
}

Upvotes: 0

iluxa
iluxa

Reputation: 6969

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.

Upvotes: 5

Related Questions