CODEWITHSUNDEEP
javarecursion
CarterZhang
CarterZhang

Reputation: 49

Get stuck on family tree using recursion

There is a family tree and I want to get the relation of two persons. For example,

enter image description here

getOneAncestry(Chaos, Uranus) returns "Uranus born of Gaia born of Chaos"

Now I have this: (I only copy part of my code, hope others will not affect) '''

    static class Individual {
    public String name;
    
    public Individual[] children;

    public Individual(String name, Individual[] children) {
        this.name = name;
        this.children = children;
    }

    boolean noChildren(){
        if (this.children == null){
            return true;
        }else{
            return false;
        }
    }

    String  getOneAncestor(Individual parent, String children){
        //if ancestor has no child
        if (parent.noChildren()){
            return null;
        }

        for (int i = 0; i < parent.children.length; i++) {
            if (parent.children[i].name.equalsIgnoreCase(children)){
                return parent.children[i].name + " born of " + parent.toString();
            }else{
                getOneAncestor(parent.children[i], children);
            }
        }

        return null;
    }


    public String toString(){
        return this.name;
    }

}

''' I'm stuck on the getOneAncestry(), I know I should use recursion, but I can't resolve it. So anyone can help me?

Upvotes: 1

Views: 739

Answers (1)

sorifiend
sorifiend

Reputation: 6307

When using recursion you need to do something with the result and return a value accordingly otherwise nothing will happen. In the code below we use the return statement to make a chain of people between the ancestor and the descendant. I have annotated what additional steps need to be taken in the code below. The key part is String result = getOneAncestor(...) and return result + " born of " + ancestor.name; as shown here:

//Input args renamed to keep it simple and clear
String  getOneAncestor(Individual ancestor, String descendant){
    //You can remove this check, the null return after the for loop takes care of this
    //if (ancestor.noChildren()){
    //    return null;
    //}

    for (int i = 0; i < ancestor.children.length; i++) {
        //Check to find the descendant
        if (ancestor.children[i].name.equalsIgnoreCase(descendant)){
            //when the descendant is found then return their name
            //The below recursive method inside the else statement will take care of the " born of " part
            return ancestor.children[i].name;
        }
        //Otherwise check the children's children for a match
        else{
            //Get the return of the recursive method so that you can do something with it
            String result = getOneAncestor(ancestor.children[i], descendant);
            
            //If a match is found in one of the children (not null returned)
            //Then we can append the " bourn of " text and return the result
            if (result != null){
                //Add the in-between relation and return the string of all relations so far in the tree
                return result + " born of " + ancestor.name;
            }
        }
    }
    //Return null if no match found within the generation
    //Or if the ancestor has no children
    return null;
}

Upvotes: 1

Related Questions