boolean recursion

Question

trying to write a boolean method that tells if someone is a decendant of someone...but can't seem to do it. of course, the object is a descendant if it's a child...or the descendant of a child.

public boolean isDescendant(member x){
    if (children.contains(x)){
        return true;
    }
    else{
        return false;
    }
}

but where or how do i insert:

for (int i = 0; i < children.size(); i++){
    isDescendant(children.get(i));
}

thanks!

Answer 1

I think what you want is below:

// Cleaned up version
public boolean isDescendant(member x){
    // check for direct descendance 
    if (children.contains(x)){
        return true;
    }
    // check for being descendant of the children
    for (Child c: children){
        if (children.get(i).isDescendant(x)) {
            return true;
        }
    }
    return false;
}

Answer 2

Walking trees is very slow downwards (from the root to the leaves). Consider this implementation for the is-ancestor check:

/**
 * Checks whether the given node is an ancestor of this node.
 */
public boolean isDescendantOf(Node ancestor) {
    Preconditions.checkNotNull(ancestor, "Ancestor");
    if (equals(ancestor)) {
        // every node is an ancestor to itself
        return true;
    } else if (parent == null) {
        // not related
        return false;
    } else {
        // recursive call
        return parent.isDescendantOf(ancestor);
    }
}

The other way is now a piece of cake.

public boolean isDescendant(Node descendant) {
    return descendant.isDescendantOf(this);
}

No loops, no exponentional effort.

PS:
In my example i would suggest renaming isDescendant to isAncestorOf.