How to convert an iterative non-dynamic method with nested for-loop to a recursive dynamic method in Java

166
June 27, 2019, at 3:30 PM

I have a class SED_PP that has an ArrayList called children which contains other SED_PP. I am trying to get write a method which can tell the user if one SED_PP object can be a child of another SED_PP object.

I have one iterative and non-dynamic method isChild(SED_PP sed) which does not go through all the arraylists in the object ad its children has.

public class SED_PP 
{
    private ArrayList<SED_PP> children = new ArrayList<SED_PP>();
    public ArrayList<SED_PP> getChildren() { return children;}
    //other methods
    public boolean IsChild(SED_PP sed)
    {
        boolean answer = false;
        if (this.children.contains(sed))
            answer = false;
        else{
            for (SED_PP s : this.children){
                if(!s.getChildren().isEmpty())
                    answer = true;
                }
            }
        }
        return answer;
    }
}

The isChild method shown does not go through all of the arraylist that parent SED_PP object has. For example, if parent A has child B, B has a child C and C has a child D, the current isChild method will not return true for A.IsChild(D) when it should be.

I think I need to use recursion for this problem but I am not very good at it.

Answer 1

You don't need recursion to solve your problem. Your code just need a fix in this part

for (SED_PP s : this.children) {
     if(!s.getChildren().isEmpty()) {
        answer = true;
     }
}

You didn't check if B has a child C and C has a child D, you only ask whether B has children or not. You should change IsChild method code this way.

public boolean IsChild(SED_PP sed)
{       
    if (this.children.contains(sed)) {
        return false;
    } 
    for (SED_PP s : this.children) {
        if (s.IsChild(sed)) {
            return false;
        }            
    }
    return true;
}  
Rent Charter Buses Company
READ ALSO
What does ConnectionShutdownException mean and how do I prevent it?

What does ConnectionShutdownException mean and how do I prevent it?

I am trying to use apache's httpclient Java libraryBut I keep getting massive numbers of ConnectionShutdownException

170
How to use CriteriaQuery Subquery Results in another Query

How to use CriteriaQuery Subquery Results in another Query

I have the following method that aggregates the total billing amount of all transactions that meet the Specification criteria (search parameters) passed into the where clause

130