recursion question

O

onetwenty8k

2[H]4U
Joined
Nov 24, 2006
Messages
2,554
I have a question this week in CS that is giving me trouble. We have to write two recursive methods, one that takes a string and prints it back with each letter separated by a comma and a space, and the other does the same thing but in reverse. I think I understand recursion but I kinda took a shortcut for the first problem and thus, the second gives me trouble. Any tips for solving are appreciated. Here is what I have.

Code: 
    public static void printLetters(String str) {
        if (str == null || str.equals("")) {
            return;
        }
        if (str.length() != 1) {
            System.out.print(str.charAt(0) + ", ");
            printLetters(str.substring(1));
        } else
            System.out.print(str.charAt(0));
    }
    
    public static void printLettersReverse(String str) {
        if (str == null || str.equals(""))
            return;
        if (str.length() >= 1) {
            printLettersReverse(str.substring(1));
            //and stuck
    }
 
onetwenty8k said:
I have a question this week in CS that is giving me trouble. We have to write two recursive methods, one that takes a string and prints it back with each letter separated by a comma and a space, and the other does the same thing but in reverse. I think I understand recursion but I kinda took a shortcut for the first problem and thus, the second gives me trouble. Any tips for solving are appreciated. Here is what I have.

Code: 
    public static void printLetters(String str) {
        if (str == null || str.equals("")) {
            return;
        }
        if (str.length() != 1) {
            System.out.print(str.charAt(0) + ", ");
            printLetters(str.substring(1));
        } else
            System.out.print(str.charAt(0));
    }
    
    public static void printLettersReverse(String str) {
        if (str == null || str.equals(""))
            return;
        if (str.length() >= 1) {
            printLettersReverse(str.substring(1));
            //and stuck
    }
Click to expand...

Save str[0] before the recursive call, then print the character after the call returns.
 
[onetwenty8k]
> I kinda took a shortcut for the first problem

Actually you didn't. Forgive me if I'm being maddeningly vague (I don't want to give up the answer too easily), but your printLetters method can be made to print in reverse by simply moving one line of code to a different place (but not actually changing the code), and then rearranging the order in which items appear in another line.

One line moved, one line (slightly) changed. The two algorithms look almost identical.

[Glimmerman]
> Save str[0] before the recursive call, then print the character after the call returns.

Not necessary, and probably against the spirit of the assignment. I think this guy's prof is trying to demonstrate how similar the algorithms can be.
 
technically saving str[0] is what you need. if you did it iteratively you could store str[0] at each iteration on a stack, and pop then all off when you're done. it's just a matter of realizing that the stack frame for each recursive call has a pointer to the a string with that information intact already, and you can access them in order from this implicit "stack" as the calls return. at which point you can move forward with Xeno8's hints
 
But when it prints backwards, I get an extra ", ". How can I avoid this with recursion?

I can do this but it gives me that extra ,
Code: 
    public static void printLettersReverse(String str) {
        if (str == null || str.equals("")) {
            return;
        }
        printLettersReverse(str.substring(1));
        System.out.print(str.charAt(0) + ", ");
    }
 
You get a comma after every character because you always print out a comma. After the last item, you don't want any more commas -- so you'll have to fix your code to print the comma conditionally instead of unconditionally.
 
I know, but I just don't know what that condition could be. I can't do length because it updates every time the recursive method is called. :(
 
mikeblas said:
You get a comma after every character because you always print out a comma. After the last item, you don't want any more commas -- so you'll have to fix your code to print the comma conditionally instead of unconditionally.
Click to expand...
Correct.
Code: 
System.out.print(str.charAt(0) + ", ");
will always print letter plus comma, even at the last letter. Some of your earlier code already started to address this, why did you drop it?
Code: 
if (str.length() != 1) {
            System.out.print(str.charAt(0) + ", ");
            printLetters(str.substring(1));
        } else
            System.out.print(str.charAt(0));

I also think I'm missing something here.
onetwenty8k said:
Code: 
    public static void printLettersReverse(String str) {
        if (str == null || str.equals("")) {
            return;
        }
        printLettersReverse(str.substring(1));    //This calls a new loop of the recursive function
        System.out.print(str.charAt(0) + ", ");   //This displays the output AFTER the new loop has been called.  How does it display every character?
    }
Click to expand...
 
The output that I want with the string say, Rabbit is

t, i, b, b, a, R

I just don't know what kind of condition will only deal with the last character in a recursive statement.
 
onetwenty8k said:
The output that I want with the string say, Rabbit is

t, i, b, b, a, R

I just don't know what kind of condition will only deal with the last character in a recursive statement.
Click to expand...
Code: 
public static void printLettersReverse(String str) {
        if (str == null || str.equals("")) {
            return;
        }
        System.out.print(str.charAt(0));
        if(str.lenght()>1)
        {
            system.out.print(", ");
            printLettersReverse(str.substring(1));
        }
}
Something more along these guidelines may work.
Furthermore, that str==null is only needed for the initial loop, when the string is first passed from the main body of your program. After that, str.length()>1 will make sure that str NEVER equals null.
 
[mikeblas]
> you'll have to fix your code to print the comma conditionally instead of unconditionally.

I disagree; his code in printLetters already prints commas conditionally. That is, if the length of str is N, he prints N - 1 commas, not N of them.

With respect to my suggestion of modifying just one line in printLetters (and relocating another), what would happen if you printed the comma before str.charAt(0) ?
 
Wouldn't you have the same problem, but moved?
That is:
, t, i, b, b, a, R

And yeah, I failed to realize that this was the Reverse function. Shouldn't be too difficult going backwards, just refer to str.charAt(str.length()-1) instead of str.charAt(0) to print and str.substring(0,str.length()-2) instead of str.substring(1) when you do your truncations.
 
onetwenty8k said:
But when it prints backwards, I get an extra ", ". How can I avoid this with recursion?

I can do this but it gives me that extra ,
Code: 
    public static void printLettersReverse(String str) {
        if (str == null || str.equals("")) {
            return;
        }
        printLettersReverse(str.substring(1));
        System.out.print(str.charAt(0) + ", ");
    }
Click to expand...

I'm not testing this, so forgive me if I'm incorrect, but here's my idea. It seems that your problem, with the Rabbit example is that you get t, i, b, b, a, R, . You don't want the comma after the R.

Consider this: What is the length of the str.substring(1) passed to printLettersReverse for the very last letter to be printed?
 
[mavalpha]
> Wouldn't you have the same problem, but moved?

Try calling printLetters somewhere else in the function.
 
Well I don't know how to store the original length so this is what is confusing me. I don't know how to say when there is only one of these methods on the stack, don't print the comma. I just don't know what the condition is for this.
 
onetwenty8k said:
Well I don't know how to store the original length so this is what is confusing me. I don't know how to say when there is only one of these methods on the stack, don't print the comma. I just don't know what the condition is for this.
Click to expand...
Why do you need to store the original length? To pass it to another part of the program, you either need to set it as a return from this function, or set aside another variable in the body of your program. If you aren't passing it anywhere, then the str.length I suggested above should take care of itself.
 
the simple solution is to use a helper function that does all the work, and on the call to the main function, it'll call this helper with a flag like isFirstChar, and the helper function calls itself with this flag always set to false. so you print the comma when isFirstChar is false, and dont print it when its true.

there's also a more elegant/straightforward approach:

on everything >except< the last recursion, print the comma >before< the character. on the last recursion, dont print any commas
 
You guys are really overcomplicating this. onetwenty8k, in printLetters, you emit output before you make a recursive function call. Try doing the opposite. Also, keep in mind the tip fluxion and I gave:

> on everything >except< the last recursion, print the comma >before<
> the character. on the last recursion, dont print any commas
 
But I don't know the condition to not print a comma on the last character!!!

I don't know how to display that in java using a recursive function....
 
Solved.
Code: 
        if (str == null || str.equals(""))
            return;
        printLettersReverse(str.substring(1));
        if (str.length() > 1)
            System.out.print(", ");
        System.out.print(str.charAt(0));
    }
 
onetwenty8k said:
But I don't know the condition to not print a comma on the last character!!!

I don't know how to display that in java using a recursive function....
Click to expand...

You do know when the recursion ends (the terminating condition). Don't print the comma on the terminating condition. Print the comma on the non-terminating condition.
 
onetwenty8k said:
Solved.
Code: 
        if (str == null || str.equals(""))
            return;
        printLettersReverse(str.substring(1));
        if (str.length() > 1)
            System.out.print(", ");
        System.out.print(str.charAt(0));
    }
Click to expand...
I'm missing one thing, must be a Java vs C++ difference. How is it displaying each character, when the printLetters() function call should re-initialize the loop before getting to the print() instruction?
 
onetwenty8k said:
Solved.
Code: 
        if (str == null || str.equals(""))
            return;
        printLettersReverse(str.substring(1));
        if (str.length() > 1)
            System.out.print(", ");
        System.out.print(str.charAt(0));
    }
Click to expand...

works, but the solution we were hinting at was a bit more obvious:

original code:
Code: 
    public static void printLetters(String str) {
        if (str == null || str.equals("")) {
            return;
        }
        if (str.length() != 1) {
            System.out.print(str.charAt(0) + ", ");
            printLetters(str.substring(1));
        } else
            System.out.print(str.charAt(0));
    }

reverse code:
Code: 
public static void printLetters(String str) {
        if (str == null || str.equals("")) {
            return;
        }
        if (str.length() != 1) {
            printLetters(str.substring(1));
            System.out.print(", " + str.charAt(0));
        } else
            System.out.print(str.charAt(0));
    }

swap 2 lines, and re-arrange the ordering of one the lines. just like Xeno8 said in the 3rd post ;p

less System.out.print() calls is a good thing, so technically it's more efficient. and i think this is the symmetry your professor had in mind in giving you this project. you'll see similar relationships when you do pre/in/post-order tree traversals
 
[fluxion]
> swap 2 lines, and re-arrange the ordering of one the lines. just like Xeno8 said in the 3rd post ;p

Thanks, fluxion. :cool:

onetwenty8k's solution is just as good as what I had in mind and even less verbose, but I liked the idea of making as few changes as possible to his printLetters method in order to get the reverse behavior.
 
You must log in or register to reply here.
Back
Top