Recursiveness in Java

Question

I’m trying to create a recursive method, which shows me all the cost centers children who do not have other children, for example:

If the father is the cost center 1, will return me the 3, 4 and 5. The 2 is not returned because he also has children.

What I’ve tried so far:

public class Teste {

    public static List<CentroCusto> centroCustos = new ArrayList<>();
    public static List<CentroCusto> centroCustos2 = new ArrayList<>();

    public static void main(String[] args) {
        build();

        CentroCusto c1 = new CentroCusto();
        c1.setId(1L);
        buscarFilhos(c1);
        System.out.println(centroCustos2);
    }

    private static CentroCusto buscarFilhos(CentroCusto ccu) {
        if (!centroCustos.stream().map(CentroCusto::getCentroCustoPai).filter(Objects::nonNull).anyMatch(centroCusto -> centroCusto.getId().equals(ccu.getId()))) {
            centroCustos2.add(ccu);
            return ccu;
        }
        for (CentroCusto centroCusto : centroCustos) {
            if (Objects.nonNull(centroCusto.getCentroCustoPai()) && centroCusto.getCentroCustoPai().getId().equals(ccu.getId())) {
                return buscarFilhos(centroCusto);
            }
        }
        return null;
    }

    private static void build() {
        CentroCusto c1 = new CentroCusto();
        c1.setId(1L);
        CentroCusto c2 = new CentroCusto();
        c2.setId(2L);
        c2.setCentroCustoPai(c1);
        CentroCusto c3 = new CentroCusto();
        c3.setId(3L);
        c3.setCentroCustoPai(c2);
        CentroCusto c4 = new CentroCusto();
        c4.setId(4L);
        c4.setCentroCustoPai(c2);
        CentroCusto c5 = new CentroCusto();
        c5.setId(5L);
        c5.setCentroCustoPai(c1);
        CentroCusto c6 = new CentroCusto();
        c6.setId(6L);
        CentroCusto c7 = new CentroCusto();
        c7.setId(7L);
        c7.setCentroCustoPai(c6);
        CentroCusto c8 = new CentroCusto();
        c8.setId(8L);
        c8.setCentroCustoPai(c7);
        centroCustos.add(c1);
        centroCustos.add(c2);
        centroCustos.add(c3);
        centroCustos.add(c4);
        centroCustos.add(c5);
        centroCustos.add(c6);
        centroCustos.add(c7);
        centroCustos.add(c8);
    }

}

public class CentroCusto {
    private Long id;
    private CentroCusto centroCustoPai;
    // Gettes e Setters
}

Answer 1

I think it gets easier if each CentroCusto have a list of children:

public class CentroCusto {
    private Long id;
    private CentroCusto pai;
    private List<CentroCusto> filhos; // lista dos filhos

    public CentroCusto(Long id) {
        this.id = id;
        // todos começam órfãos e sem filhos
        this.filhos = new ArrayList<>();
        this.pai = null;
    }

    public void addFilho(CentroCusto filho) {
        this.filhos.add(filho); // adiciona na lista de filhos
        filho.pai = this; // atualiza o pai do filho recém-adicionado
    }

    public boolean temFilhos() {
        return this.filhos.size() > 0;
    }

    public Long getId() {
        return id;
    }

    public CentroCusto getPai() {
        return pai;
    }

    public void mostrarDescendentesSemFilhos() {
        for (CentroCusto c : this.filhos) {
            if (c.temFilhos()) {
                c.mostrarDescendentesSemFilhos();
            } else {
                System.out.println(c.getId());
            }
        }
    }
}

I also created a builder that receives the id, and created a method that adds a child (and note that this method already updates the pai of CentroCusto added as child).

And I removed the setters, because they don’t seem necessary to me (someone can change pai or of id deliberately? ). Anyway, details...

---

This makes it easier to recur (I changed the method name to mostrarDescendentesSemFilhos, because deep down that is what he does, since he can show a grandson, great-grandson, etc., and not just a direct child). The idea is to go through the list of children, and for each one:

• if you don’t have children, show
• if it has, call the method recursively, so it will go through the children of the child (and see if they have descendants, calling the method again if necessary, and so on)

The method now is void because it returns nothing, only prints. It made no sense for it to return a single CentroCusto, since it can actually have more than one. So no main would look like this:

CentroCusto c1 = new CentroCusto(1L);
CentroCusto c2 = new CentroCusto(2L);
c2.addFilho(new CentroCusto(3L));
c2.addFilho(new CentroCusto(4L));
c1.addFilho(c2);
c1.addFilho(new CentroCusto(5L));
CentroCusto c6 = new CentroCusto(6L);
CentroCusto c7 = new CentroCusto(7L);
c7.addFilho(new CentroCusto(8L));
c6.addFilho(c7);

System.out.println("Descendentes de c1:");
c1.mostrarDescendentesSemFilhos();  // imprime 3, 4 e 5
System.out.println("Descendentes de c6:");
c6.mostrarDescendentesSemFilhos(); // imprime 8

---

If instead of printing, you want to return the objects themselves, then the method should return a list:

public class CentroCusto {
    ... o resto do código é igual

    public List<CentroCusto> getDescendentesSemFilhos() {
        List<CentroCusto> list = new ArrayList<>();
        for (CentroCusto c : this.filhos) {
            if (c.temFilhos()) {
                // tem filhos, procura pelos descendentes recursivamente e adiciona na lista
                list.addAll(c.getDescendentesSemFilhos());
            } else {
                list.add(c); // não tem filhos, adiciona na lista
            }
        }
        return list;
    }
}

Only now on the main you will need to go through the list if you want to know which are:

System.out.println("Descendentes de c1:");
// imprime 3, 4 e 5
for (CentroCusto c : c1.getDescendentesSemFilhos()) {
    System.out.println(c.getId());
}
System.out.println("Descendentes de c6:");
// imprime 8
for (CentroCusto c : c6.getDescendentesSemFilhos()) {
    System.out.println(c.getId());
}

Answer 2

I think I got it, I’ll post the source:

public class Teste {

    public static List<CentroCusto> centroCustos = new ArrayList<>();
    public static List<CentroCusto> centroCustos2 = new ArrayList<>();

    public static void main(String[] args) {
        build();
        CentroCusto c1 = centroCustos.get(0);
        imprimirRecursivamente(c1);

        for (CentroCusto centroCusto : centroCustos2) {
            if (isFilho(centroCusto)) {
                System.out.println(centroCusto.getId() + " é filho.");
            }
        }
    }

    private static void imprimirRecursivamente(CentroCusto cc) {
        for (CentroCusto filho : getFilhos(cc)) {
            imprimirRecursivamente(filho);
            centroCustos2.add(filho);
        }
    }

    private static List<CentroCusto> getFilhos(CentroCusto cc) {
        List<CentroCusto> ccus = new ArrayList<>();
        for (CentroCusto centroCusto : centroCustos) {
            if (Objects.nonNull(centroCusto.getCentroCustoPai()) &&
                    centroCusto.getCentroCustoPai().getId().equals(cc.getId())) {
                ccus.add(centroCusto);
            }
        }
        return ccus;
    }

    private static boolean isFilho(CentroCusto ccu) {
        return !centroCustos.stream().map(CentroCusto::getCentroCustoPai).filter(Objects::nonNull).anyMatch(centroCusto -> centroCusto.getId().equals(ccu.getId()));
    }

    private static void build() {
        CentroCusto c1 = new CentroCusto();
        c1.setId(1L);
        CentroCusto c2 = new CentroCusto();
        c2.setId(2L);
        c2.setCentroCustoPai(c1);
        CentroCusto c3 = new CentroCusto();
        c3.setId(3L);
        c3.setCentroCustoPai(c2);
        CentroCusto c4 = new CentroCusto();
        c4.setId(4L);
        c4.setCentroCustoPai(c2);
        CentroCusto c5 = new CentroCusto();
        c5.setId(5L);
        c5.setCentroCustoPai(c1);
        CentroCusto c6 = new CentroCusto();
        c6.setId(6L);
        CentroCusto c7 = new CentroCusto();
        c7.setId(7L);
        c7.setCentroCustoPai(c6);
        CentroCusto c8 = new CentroCusto();
        c8.setId(8L);
        c8.setCentroCustoPai(c7);
        centroCustos.add(c1);
        centroCustos.add(c2);
        centroCustos.add(c3);
        centroCustos.add(c4);
        centroCustos.add(c5);
        centroCustos.add(c6);
        centroCustos.add(c7);
        centroCustos.add(c8);
    }

}