get wrong output of a recursive method

Question

    public static int getIndexOf(char ch, String str) {
    if (str == null || str.equals("")) {
        return 0;
     //base case
    }else{
        char first = str.charAt(0);
        if (ch != first) {
            return -1;
     //returns -1 when the character cannot be found within the string
        }else{
            int rest = str.length() - 1;
            if (str.charAt(rest) == ch) {
                return rest; 
            }
            return lastIndexOf(ch, str.substring(0, rest));
            //recursive case
        }
    }
}

This my method which returns the index of the input character of the input string. However, when I run it in the interaction plane, it returns wrong number. For example, when I enter 'a' and "peach", it is supposed to return 2, but it returns -1. This method should return -1 only when the character cannot be found in the string. Can anyone tell me how to deal with it? Thank you!

If you want the index of a in peach, you'll jump into the else block (because peach is not null and it's not equal to ""). There the first character (p) is compared to a, which are not equal. Therfore the if condition is true and your method will return -1. — jlordo
– jlordo, Commented Apr 5, 2013 at 0:40
Second of all, of course you are getting a -1 instead of two... you execute that method and if returns -1 when ch != first — jsedano
– jsedano, Commented Apr 5, 2013 at 0:40

Porkbutts · Accepted Answer · 2013-04-05 00:40:03Z

1

Well why don't you step through the logic and see what happens.

getIndexOf('a', "peach")

Method goes in, string isn't null or empty so it falls through to the next line of code.

char first = str.charAt(0); // this is 'p'

if (ch != first) {  // is 'p' equal to 'a'? no. so return -1
        return -1;

And then the rest of your logic will never execute. Can you see how to fix this problem?

answered Apr 5, 2013 at 0:40

Porkbutts

9747 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

nommyravian · Accepted Answer · 2013-04-05 00:42:19Z

0

your following portion of code means that it will check for the first character of the string if it is matching otherwise it will return -1.

char first = str.charAt(0);
        if (ch != first) {
            return -1;

this says that if character at 0th index doesn't match then send -1 so as 'p' in "peach" isn't matching with 'a' so it is return -1.

did you get it?

answered Apr 5, 2013 at 0:42

nommyravian

1,3562 gold badges13 silver badges30 bronze badges

1 Comment

ymazing Over a year ago

Yes, but how do I deal with it?

Gene · Accepted Answer · 2013-04-05 00:59:43Z

The output's not wrong, the implementation is!

Think in words first. If the desired character is the first character in the string, then the result is zero. Otherwise it's (1 + the index in the string that remains after cutting off the first character). Now code the words:

return (str.charAt(0) == ch) ? 0 : 1 + getIndexOf(ch, str.substring(1));

This doesn't yet handle the case where the character is not in the string at all. Here the charAt(0) call will eventually throw IndexOutOfBoundsException because str doesn't have one!

The cleanest way to handle this case is to catch the exception. So you's have two functions: mustGetIndexOf, which is the recursive relation above, and getIndexOf, which calls the one above inside a try {} catch() {}, returning -1 in that case.

Of course if you don't want to allow the exception, you can test the recursive call's result with if for the special case of -1. The code is uglier, but it will work. Whenever a -1 is seen, return -1 again. This propagates the -1 all the way back to the caller. The exception "unwinds" the recursive calls on the stack in a similar manner, just with one chop instead of the gradual call-by-call way your if statements will do it.

I won't give you full code so you can continue to learn.

Collectives™ on Stack Overflow

get wrong output of a recursive method

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related