Java && || in RETURN statements?

Question

I'm looking at some Java algorithm examples and I come across this snippet code within a recursive method:

boolean subTree(TreeNode t1, TreeNode t2) {
    if (t1 == null) {
        return false;
    }
    if (t1.value == t2.value) {
        if (treeMatch(t1, t2))
            return true;;
    }
    return (subTree(t1.left, t2) || subTree(t1.right, t2));
}

Not knowing (and never seeing) || being used within a return statement before, let alone a recursive one, really made me confused. I copied the code into Eclipse to see if it was valid and it was. I then replaced the || with && and Eclipse didn't seem bothered by it. Logically, I understand that this recursive code is supposed to continue down the left and right subtrees of TreeNode t1, but I'm looking for a more theoretical explanation behind how this Java syntax works.

Can someone explain the meaning behind || and && within Java's return statement? What does it mean in terms of recursion? Is it only meaningful when used in conjunction with recursion?

Solution 1

As defined in the method signature, you will have to return a boolean. Therefore, after the return keyword, you will have to provide a boolean or an expression which is evaluated to boolean.

In your case you have the expession (subTree(t1.left, t2) || subTree(t1.right, t2)); in which the two operands will be evaluated to boolean and you will apply an logical OR on them only if the first evaluates to false. If the first operand evaluates to true the second will not be evaluated and true will be retured.

Solution 2

They work the same way, whether there is a recursive statement in there or not. In your expression:

(subTree(t1.left, t2) || subTree(t1.right, t2))

if the first call to subTree(t1.left, t2) evaluates to true, the second expression won't be called or attempted to be evaluated. This is just the standard short-circuit behaviour of the || and && operators and is how the operators work with any arguments given to them.

Comments

[rsenna]

+1 The short-circuit behavior info is pretty relevant since we're talking about a recursive call.