CODEWITHSUNDEEP
javarecursioniteration
Jonny
Jonny

Reputation: 61

Traverse inheritance tree recursively with Java

I need to take a given record and populate a list with the identifiers of all of its child records ad infinitem (I.e. all child records of original item, all child records of children, all child records of grandchildren etc.) I currently have a method which produces what I want but it's not the most easily read and uses iteration rather than recursion. I'm wondering if there is a cleaner way to achieve what I want, potentially using a recursive call but with the primary aim of making the code easier to read. Current implementation is as follows

public List<String> getAllChildRecords(targetRecord) {  
    
    final List<String> allChildRecordIds = new ArrayList<>();
    final List<String> recordIdsForQuery = new ArrayList<>();
    final List<String> queryResults = new ArrayList<>();

    recordIdsForQuery.add(targetRecord);

    while (!recordIdsForQuery .isEmpty()) {

        for (final String queryParentId : recordIdsForQuery ) {
            queryResults.addAll(
                    [DBAccessLayerClass].[getChildRecordIds](queryParentId));
        }

        allChildRecordIds .addAll(queryResults);
        recordIdsForQuery .clear();
        recordIdsForQuery .addAll(queryResults);
        queryResults.clear();
    }

    return allChildRecordIds

}

Upvotes: 0

Views: 94

Answers (1)

rzwitserloot
rzwitserloot

Reputation: 102832

Recursion isn't usually the right answer, especially in java - it tends to be slow, for example, and produce convoluted stack traces. Therefore, 'just rewrite to recursion' is not the slamdunk answer, and thus, not a slamdunk improvement if you're concerned about readability.

The usual trick is to work with a queue. Also, stop declaring things final 'for readability' - you're adding a ton of noise to this code. If you insist on having 'changing locals' be reduced to a minimum for readability, configure your IDE to render writes to locals in a highly visible manner, don't mess up your code by adding a bunch of noisy keywords everywhere.

var out = new ArrayList<String>();
var queue = new ArrayDeque<String>();
queue.add(targetRecord);

while (!queue.isEmpty()) {
  String id = queue.pop();
  var childIds = DbAccessLayerClass.getChildRecordIds(id));
  out.addAll(childIds);
  queue.addAll(childIds);
}

return out;

If you're afraid of loops or repeats (where 1 item can be a child of multiple separate entries, for example), turn your out into a (Linked)HashSet instead, and add childIds.removeAll(out); right after DbAccessLayerClass.getChildRecordIds.

Upvotes: 1

Related Questions