[slickProcrastinator]

Long time listener, first time caller />

As part of a homework assignment, I need to use recursion to solve a problem. I have written a method that works, but am not quite sure if I have applied the concept for recursion correctly in this situation. I have included the problem description and my code with comments (along with a main() runner program). Please let me know if this is considered "recursion."

Assignment:
Given a string, return recursively a "cleaned" string where adjacent chars that are the same have been reduced to a single char. So "yyzza" yields "yza".

stringClean("yyzzza") -> "yza"
stringClean("abbbcdd") -> "abcd"
stringClean("Hello") -> "Helo"

 

public static void main(String[] args) {
     System.out.println("Cleaning yyzzza: " + stringClean("yyzzza"));
     System.out.println("Cleaning abbbcdd: " + stringClean("abbbcdd"));
     System.out.println("Cleaning Hello: " + stringClean("Hello"));
}

/**
     * Recursive method to remove consecutive duplicate characters from a
     * string. Beginning at string index 1, compare to previous string
     * character. If they match (case sensitive) call method again with the
     * character removed from the string. Character is removed by concatenating
     * the substring up to that duplicate character with the remainder of the
     * string after that character.
     * @param str // the string to check for consecutive duplicate characters
     * @return a string with no consecutive duplicates
     */
    private static String stringClean(String str) {
        // Search for a duplicate character
        for(int i = 1; i < (str.length()); i++) {
            if(str.charAt(i-1) == str.charAt(i))
                // Remove the duplicate character and search again
                return stringClean(str.substring(0, i-1) + 
                        str.substring(i, str.length()));
        }
        
        // Base case has no duplicate characters
        return str;        
    }

[Martyr2]

Yup, you have a base case and a body which calls itself. By all definition this is recursion.

[cfoley]

I'm going to say no.

You do have a recursive call. Nobody can argue about that but the important algorithmic stuff is iterative. I guess you have a mixture of recursive and iterative code in there. If I were to rewrite that as recursive, my thinking might be a bit like this:

For loops aren't recursive. If I want to iterate over a string, I need to remove the first character in each recursive call. My base case becomes an empty string. If I wanted to write a function that removed all the characters of a certain type from a string, it might look like this (and this or something like it might be a useful helper function for your overall problem):

	public String removeAll(char c, String s) {
		
		// base case
		if ("".equals(s)) {
			return "";
		}
		
		// recursive case
		char firstChar = s.charAt(0);
		String remainder = s.substring(1);
		
		if (c == firstChar) {
			return removeAll(c, remainder);
		} else {
			return firstChar + removeAll(c, remainder);
		}
	}

[pbl]

I don't think that there is a law saying that a recursive function cannot have a for/while loop inside itself
May be baavgai has something to day about it

[cfoley]

You are right, of course, and so is Martyr2. However, the question was qualified by the statement that for this homework they have to use recursion to solve the problem. I could be wrong but I think it means recursion as opposed to iteration, otherwise what is the point of the exercise.

It would be quite natural to use a nested for loop to solve this problem. The OP has replaced the outer loop with recursion and left the inner loop iterative. If the marking scheme is something like the one I imagine (perhaps weighted differently) then he still has some work to do:

2 marks: correct answer from method
2 marks: one recursive call
1 mark: no iteration (usually 2 recursive calls but could be an over-complex helper function)

[burakaltr]

I Have Done a Similar one like this, non-recursively

It's Brilliant, what your recursive program does

For ScreenShots :


http://postimage.org/image/oqvndq9g3/

[baavgai]

pbl, on 09 March 2013 - 07:54 PM, said:

May be baavgai has something to day about it

Nah. cfoley nailed it. A loop is generally a recursion fail.

It would be hard to give an example of the solution without just giving it up. I can describe it...

Basically, you keep calling yourself, whittling the string down one character at a time, from the top. On the way back up, you check to see if the string coming back up has the same letter at the top as the one you're looking at. If it does, you just keep passing back, if not then you tack on the letter and pass back.

Hope this helps.

[jon.kiparsky]

cfoley has it right.

The key insight about recursion is that it defines the problem in terms of an induction: there is one case which you know the answer to, and any other case that you're interested in can be reduced to that case.

[slickProcrastinator]

Thank you all for your responses - cfoley, you were able to put better into writing what I couldn't explain. I liked your solution suggestion, however I didn't want the application program to worry about passing anything except the string. In fact, my first attempt at a solution involved passing the string along with an index number that kept track of the position being tested. This way I didn't have iteration, but I still wasn't happy with the extra parameter.

baavgai, your explanation was helpful to get me thinking about this in the right way. Here is what I came up with:

private static String stringClean(String str) {
        // Base case: String is of length 1
        if(str.length() == 1)
            return str;
        
        // General case: If the first 2 characters are equal, return stringClean
        // of the substring without the first character (this will remove the
        // duplicate character from the string.) If the first two characters are
        // not equal, return the first character concatenated  with the 
        // stringClean of the substring without the first character.
        if(str.charAt(0) == str.charAt(1))
            return stringClean(str.substring(1));
        return str.charAt(0) + stringClean(str.substring(1));
}

Again, thanks to all!

[cfoley]

That solution looks very good. There is a small problem in that you will get an exception if it is passed the empty string as the argument. I misread the question and didn't notice the critical word "adjacent" so the helper method I recommended is totally inappropriate.

[slickProcrastinator]

cfoley, on 10 March 2013 - 04:31 PM, said:

There is a small problem in that you will get an exception if it is passed the empty string as the argument.

I will add the precondition that the string may not be empty. Thank you for pointing that out!

[cfoley]

I hope you really mean you will make it work with zero length strings. It's a one-character change!

[slickProcrastinator]

Though I like your suggestion, I am going to have the application level handle this exception (this makes more sense for the overall assignment.)

[baavgai]

???

A check should be your very first line:

private static String stringClean(String str) {
	if (str==null || str.length()==0) { return ""; }

Your return also need check for str.length()==0, because that will (obviously, given the above ) be the last value returned at the bottom of the recursive stack.