How to collect the result of a recursive method

Question

I iterate through a tree structure to collect the paths of the leaf nodes. Which way do you prefer to collect the result of the operation:

a) merge the results of the children and return this

private Collection<String> extractPaths(final Element element, final IPath parentPath) {
    final IPath path = parentPath.append(element.getLabel());
    final Collection<Element> children = getElementChildren(element);
    if (children.isEmpty())
        return Collections.singletonList(path.toString());

    final Set<String> result = new TreeSet<String>();
    for (final Element child : children)
        result.addAll(extractPaths(child, path));
    return result;
}

b) provide the result collection as a parameter and add new elements in each recursion step

private void extractPaths(final Element element, final IPath parentPath, final Set<String> result) {
    final IPath path = parentPath.append(element.getLabel());
    final Collection<Element> children = getElementChildren(element);
    if (children.isEmpty())
        result.add(path.toString());

    for (final Element child : children)
       extractPaths(child, path, result);
}

Answer 1

Both can be used without any problems. Though, former solution is more clean since it doesn't change input parameters. No side effects is in the nature of functional programming.

Answer 2

I assume the latter is meant to call extractPaths(child, path, result)?

The latter form will be more efficient, as it doesn't need to copy items at every level of recursion. As Boris says, it's less functionally clean - but Java doesn't really provide immutable collections with appropriate methods to create new collections based on them efficiently.

In terms of making it pleasant to call, you could provide a wrapper in the style of the first option which just creates a new set and calls the second option. That's probably what I'd do:

private Collection<String> extractPaths(Element element, IPath parentPath) {
    Set<String> ret = new HashSet<String>();
    extractPaths(element, parentPath, ret);
    return ret;
}

Another alternative is to change the third parameter from a Set<String> to some sort of "collector" interface: you tell it that you've found a result, without specifying what to do with it. Indeed, the collector could return a new collector to use from then on - leaving it up to the implementation to decide whether to make a functionally-clean "create a new set" version, or hide side-effects in the collector which would just return itself again for reuse.