A recursive method in java

Discussion in 'Mac Programming' started by milk242, Apr 19, 2009.

  1. milk242 macrumors 6502a

    Joined:
    Jun 28, 2007
    #1
    I was wondering if someone could help me go through my wrong logic in this code. I am trying to take a string and remove all the vowels using a recursive method.

    Code:
    # public static void RemoveVowels(String str)
    #      if (str.substring(0,1).compareToIgnoreCase("a" == 0))
    #      {
    #           str.replace("a", "");
    #           RemoveVowels(str.substring(1));
    #      }
    #      else
    #           RemoveVowels(str.substring(1));
    My reasoning is that if the character at beginning of string is not "a" then it'll execute the else statement and make the sentence one character shorter. Once it reaches an "a", it'll remove it and make the string one letter shorter.
     
  2. Wes macrumors 68020

    Wes

    Joined:
    Jun 22, 2001
    Location:
    London
    #2
    Why not this:

    Code:
    public String removeVowels(String s) {
       return s.replaceAll("[aeiou]","");
    }
    
    Saves you having to mess around. I see some problems in your logic (strings are immutable and your function is void, etc.) but I need to get out the door in 2 minutes, hope somebody else can help with that.
     
  3. WhiteRabbit macrumors newbie

    Joined:
    Jan 11, 2005
    #3
    Shouldn't it be (blah("a") == 0) instead of (blah("a" == 0))?

    At some point the string will be only one character. Does the program just crash, what happens then. You might want to check for that.
    I don't know Java, but it looks like you're modifying an instance variable in each instance of the method and not returning it.

    Also, a recursive fiction seems like an inefficient solution to the original problem.
     
  4. milk242 thread starter macrumors 6502a

    Joined:
    Jun 28, 2007
    #4
    Yea I know you can do it with regular expressions or even just use str.replace("a", ""), but I'm working out of a book and I'm on the chapter for recursion. I would just like to figure this out.
     
  5. lazydog macrumors 6502a

    Joined:
    Sep 3, 2005
    Location:
    Cramlington, UK
    #5
    Hi

    replace() returns a new string, it doesn't do the replacement on the source string itself.

    But replace() isn't what you want to use anyway if it's an exercise in recursion. Have a read of the documention for replace() to see why.

    b e n
     
  6. aliher macrumors newbie

    Joined:
    Mar 25, 2009
    Location:
    UK
    #6
    If you want to build strings you should look on the StringBuilder to build result of your recursion. All string operations create new strings so it may be quite an expensive thing to do that will stress the GC.
     
  7. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #7
    I won't write the helper methods, but I would see a recursive solution looking something like this:

    Code:
    java.lang.String removeVowels(java.lang.String src) {
      if(src == null) return ""; //Base case/input validation
      if(src.length() == 0) return ""; //Base case
      if(src.length() == 1) { //Base case
        if (isVowel(src.charAt(0)) {
          return "";
        } else {
          return src;
        }
      }
      if(isVowel(src.charAt(0)) { //length > 1, recursive case
        return removeVowels(src.substring(1));
      } else {
        return src.charAt(0) + removeVowels(src.substring(1));
      }
    }
    This isn't the most efficient (at all), since you're going to be building a lot of new Strings that will be immediately discarded. I don't think that's the point of the exercise, though. Obviously there are built in methods for doing this, but the point of this was recursion.

    Note that i didn't run this or test it, it could have some devastating bug in it... but that should be the general idea. The way I approach recursion (the few times i do so in iterative languages) is to clearly chart out error cases and base cases and decide how to deal with them. Just because you don't think a String with 0 length will be passed in doesn't mean this shouldn't be handled cleanly. Once you've mapped out your base cases, then you have to deal with your recursive case. At this point some amount of work should be done, and "less" work should be passed to a new instance of your function.

    Note that in a language that doesn't implement zero stack growth tail recursion, you're using a chunk of memory each time you hit your recursive case. This means that if you have a String that's a few thousand characters long, you may start running into issues with the stack. I'm not sure how the JVM will deal with this, to be honest. It may grow the stack space, and you'll have room up until the maximum memory, it may throw an OutOfMemory exception or something, etc. Just something to be aware of.

    -Lee

    EDIT: There was quite a bit of discussion about stack growth here that might be of interest:
    http://forums.macrumors.com/showthread.php?t=561251
     
  8. wolfenkraft macrumors regular

    Joined:
    Mar 6, 2008
    #8
    That looks reasonable from a conceptual stand point. Rule 1 when dealing with recursion is set up your base cases. Everything that involves recursion and a list should start with a "is null?" and/or "is length==0?" that's pretty much universal regardless of language.
     

Share This Page