Recursion and if statement in java

Question

I am implementing recursive Binary Search in Java using ArrayList. Here is my code:

public static boolean binarySearchRecursive(List<Integer> list, int item) {
    int midpoint = (list.size()) / 2;
    System.out.println(list.get(midpoint));
    if (list.get(midpoint) == item) {
        return true;
    } else if (list.get(midpoint) > item) {
        binarySearchRecursive(list.subList(0, midpoint), item);
    } else if (list.get(midpoint) < item) {
        binarySearchRecursive(list.subList(midpoint + 1, list.size()), item);
    }
    return false;
}

Then I call binarySearchRecursive providing arguments: ArrayList with size = 1 000 000, where index == value; and item == 64327. Console output is:

... 64241, 64317, 64355, 64336, 64327

So I see midpoint got value of item and method should return true after comparation, but method constantly return false. What is pecularity of this method? Why code proceeds until last return statment, and return false from there instead of return true from 5th line?

T.J. Crowder · Accepted Answer · 2015-10-03 13:20:20Z

A couple of problems there:

You need to return the result of your recursive calls. Right now, you're just calling binarySearchRecursive and then returning false — which is a problem if they found something and returned true!

The general form of a recursive function/method is this:
```
ResultType method(data) {
    if (condition_that_ends_recursion) {
        return positive_result;
    }
    return method(new_data_function_should_work_with);
}
```
Note that when calling itself, method returns the result of the recursive call.
At some point, you're going to run out of entries to check (e.g., the sublist will be zero), but your code isn't allowing for that, it assumes the list will always have at least one entry. You need to account for that condition as well in your logic.

Side note: If you have a return in an if branch, there's no need to use else for the next condition.

Side note 2: You have if (list.get(midpoint) == item) and then else if (list.get(midpoint) > item), so there's no need for else if (list.get(midpoint) < item); just else is all you need there. If it's not ==, and it's not >, you know for sure it's <.

Afsin Buyuksarac · Accepted Answer · 2015-10-03 12:55:19Z

1

you need to return the result of the callee as the result of the main caller.

    public static boolean binarySearchRecursive(List<Integer> list, int item) {
    int midpoint = (list.size()) / 2;
    System.out.println(list.get(midpoint));
    if (list.get(midpoint) == item) {
        return true;
    } else if (list.get(midpoint) > item) {
        **return** binarySearchRecursive(list.subList(0, midpoint), item);
    } else if (list.get(midpoint) < item) {
        **return** binarySearchRecursive(list.subList(midpoint + 1, list.size()), item);
    }
    return false;
}

Without these return statements it just returns from the sub method true, but goes to the end main method returns FALSE

answered Oct 3, 2015 at 12:55

Afsin Buyuksarac

2981 silver badge10 bronze badges

4 Comments

T.J. Crowder Over a year ago

That's half the problem. :-)

Afsin Buyuksarac Over a year ago

your answer very protective and conservative :) I set him free to guess rest of the his errors. He needed to know what is the problem :) New guys need to dig the internet and code much. They ask and want whole bunch of code.

T.J. Crowder Over a year ago

You'll note I didn't actually code anything for him. :-)

Afsin Buyuksarac Over a year ago

heyyy that was just copy/past engineering though ! I wasnt coding :) By the way my vote is for you :)

Collectives™ on Stack Overflow

Recursion and if statement in java

2 Answers 2

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related