CODEWITHSUNDEEP
javaif-statementrecursion
Rudziankoŭ
Rudziankoŭ

Reputation: 11251

Recursion and if statement in java

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?

Upvotes: 1

Views: 1681

Answers (2)

T.J. Crowder
T.J. Crowder

Reputation: 1074258

A couple of problems there:

  1. 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.

  2. 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 <.

Upvotes: 3

Afsin Buyuksarac
Afsin Buyuksarac

Reputation: 298

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

Upvotes: 1

Related Questions