Stop a recursive method when a certain condition is met

Question

I have a class called Item, and it's defined as following :

public class Item {
  private Long id;
  private String text;
}

And it's DTO is as following :

public class ItemDTO {
  private String id;
  private String text;
  private List<ItemDTO> children;
}

So using a DAO function I will retrieve an object children using it's id from database, as following :

List<Item> children = itemDAO.findChildrenForItem(id);

And for each child I will retrieve it's children and so on..., for that I created a recursive function, which worked in this case :

public List<ItemDTO> process(Long id) {
    List<ItemDTO> list = new ArrayList<>();

    // Get children
    List<Item> children = itemDAO.findChildrenForItem(id);

    if (children != null && children.size() > 0) {
      for (Item child : children) {
        ItemDTO dto = new ItemDTO();
        dto.setId(String.valueOf(child.getId()));
        dto.setText(child.getLib());
        dto.setChildren(process(child.getId()));
        list.add(dto);
      }
    }

    return list;
  }

Here what I want to do is that when I reach the 5th iteration in the recursive method to stop and move to the next element in the children array.

So the first level children will have 4 level children, and the second level children will have 3 level children and so on..., so this is what I tried :

public List<ItemDTO> process(Long id, Integer level) {
    List<ItemDTO> list = new ArrayList<>();

    // Get children
    List<Item> children = itemDAO.findChildrenForItem(id);

    if (children != null && children.size() > 0) {
      for (Item child : children) {
        level = level != null ? level : 0;
        ItemDTO dto = new ItemDTO();
        dto.setId(String.valueOf(child.getId()));
        dto.setText(child.getLib());
        level++;
        dto.setChildren(level <= 4 ? process(child.getId(), level) : null);
        list.add(dto);
        level = 0;
      }
    }

    return list;
  }

But this didn't work I always get children more than the forth level.

How can I solve this ?

score 1 · Accepted Answer · answered Nov 29 '17 at 15:34

You're never checking the value of level to see if it's reached your goal. You also seem to be overcomplicating the use of that level variable. Consider a structure like this:

public List<ItemDTO> process(Long id, Integer level) {
    List<ItemDTO> list = new ArrayList<>();

    // check the recursive logic's terminating condition
    if (level == 5) {
        // reached the intended bottom, return
        return list;
    }

    List<Item> children = itemDAO.findChildrenForItem(id);
    if (children != null && children.size() > 0) {
        for (Item child : children) {
            level = level != null ? level : 0;
            ItemDTO dto = new ItemDTO();
            dto.setId(String.valueOf(child.getId()));
            dto.setText(child.getLib());

            // you don't need a lot of logic here, just increment the level in the recursive call
            dto.setChildren(process(child.getId(), level + 1));

            list.add(dto);
        }
    }

    return list;
}

So when the target "level" is reached, the method doesn't bother finding the children and simply returns an empty list. (Or you can return null, or something else, that's up to you.) Then in the recursion to the next "level" all you need to do is add 1 to the current "level".

Essentially it looks like you were trying to have a single global variable which knows the full state of the recursion, and base logic off of that. Instead, have the recursive method itself simply know when to stop based on the value that's passed to it. And just pass the modified value each time.

So let's say when iterating `children` in this line : `for (Item child : children) {` for the first iteration in this loop, the `level` var will reach `5` and the recursive function will return a null, so it will never move to the second element in the `children` array — Renaud is Not Bill Gates, Nov 29 '17 at 15:42
@AimadMAJDOU: Why wouldn't it? `dto.setChildren(/.../)` will set the children for *that item* to whatever the recursive call returns (null or an empty list, your choice). But the loop will still move on to the next element in the *current method call's* array. It'll simply pass `5` (`level + 1`) to each element in that array's recursive method call. Thus setting each element's "children" to null or an empty array. And then return back up the stack. Isn't that exactly the behavior you're looking for when you reach the maximum level? — David, Nov 29 '17 at 15:44
Sorry my bad, I meant to ask for how it will work in that case, now your answer made it clear, thanks for your help, I appreciate that. — Renaud is Not Bill Gates, Nov 29 '17 at 15:50

score 0 · Answer 2 · answered Nov 29 '17 at 15:56

In general, the first task of a recursive method should be to stop the recursion and return to the caller. Then, do the work for the current step in the recursive call stack if you are not returning immediately.

That said, you could also let the database do this for you with a hierarchical query. This would bring all your data back in one resultset and eliminate the need for multiple calls to the db.

Something along the lines of this for Oracle:

select id, text, LEVEL
from items
where LEVEL < 5
start with id = ?
connect by prior parent_id = id
order siblings by ...

For MySQL, there is a similar option. See this for example - How to create a MySQL hierarchical recursive query

Yes, doing it with SQL would of been better, but due to unavoidable technique constraints (since I'm using JPA Criteria API) I can't do that unfortunately. — Renaud is Not Bill Gates, Nov 29 '17 at 16:22

Stop a recursive method when a certain condition is met

2 Answers2