Как собрать результат рекурсивного метода

Оба могут использоваться без каких-либо проблем. Впрочем, первое решение более чистое, так как не меняет входных параметров. Функциональное программирование не имеет побочных эффектов.

Я предполагаю, что последний предназначен для вызова extractPaths (child, path, result) ?

Последняя форма будет более эффективной, так как она не требует для копирования элементов на всех уровнях рекурсии. Как говорит Борис, он менее функционально чист, но Java на самом деле не предоставляет неизменяемые коллекции с соответствующими методами для эффективного создания новых коллекций на их основе.

С точки зрения удобства вызова, вы могли бы предоставить оболочку в стиле первого варианта, который просто создает новый набор и вызывает второй вариант. Вероятно, это то, что я бы сделал:

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

Другой альтернативой является изменение третьего параметра с Set на какой-то интерфейс «сборщика»: вы говорите ему, что нашли результат , не уточняя, что с этим делать. Действительно,

To provide the most convenient and flexible interface to your clients, write it as a class that implements Iterator.

This means that the client can loop through the items found during the recursion, but they don't have to implement their "for each" code as a callback (Java doesn't have a pretty way to do that), and they can even "pause" the operation and continue it later, outside of the scope in which they began it (or abandon it at any point).

It's the trickiest to implement though. If the data structure you're traversing is a tree-like structure with parent pointers in each node then you need no other data than the current node. To get to the next node, look for a first child. If there is one, that's the next node. Otherwise try the next sibling. If there isn't one, get the parent and try to get its next sibling, and so on until you hit a null in which case there are no more items.

As a quick and dirty example, here's a treenode-like class, breaking all the rules about encapsulation to save some space here:

class SimpleNode
{
    String name;
    public SimpleNode parent, firstChild, nextSibling;

    public SimpleNode(String n) { name = n; }

    public void add(SimpleNode c)
    {
        c.parent = this;
        c.nextSibling = firstChild;
        firstChild = c;
    }

    public String getIndent()
    {
        StringBuffer i = new StringBuffer();

        for (SimpleNode n = this; n != null; n = n.parent)
            i.append("  ");

        return i.toString();
    }
}

Now let's create a tree from it:

SimpleNode root = new SimpleNode("root");

SimpleNode fruit = new SimpleNode("fruit");
root.add(fruit);
fruit.add(new SimpleNode("pear"));
fruit.add(new SimpleNode("banana"));
fruit.add(new SimpleNode("apple"));

SimpleNode companies = new SimpleNode("companies");
root.add(companies);
companies.add(new SimpleNode("apple"));
companies.add(new SimpleNode("sun"));
companies.add(new SimpleNode("microsoft"));

SimpleNode colours = new SimpleNode("colours");
root.add(colours);
colours.add(new SimpleNode("orange"));
colours.add(new SimpleNode("red"));
colours.add(new SimpleNode("blue"));

Now, to spell this out for anyone new to this idea, what we want to be able to do is this:

for (final SimpleNode n : new SimpleNodeIterator(root))
    System.out.println(n.getIndent() + "- " + n.name);

And get this (I've made the above code generate something that looks like a hierarchical bullet list in SO):

• root
  • цветов
    • синий
    • красный
    • оранжевый
  • компании
    • microsoft
    • солнце
    • яблоко
  • фрукты
    • apple
    • banana
    • pear

To do this, we have to map some standard operations onto our SimpleNode class:

class SimpleNodeIterator extends TreeIterator<SimpleNode>
{
    public SimpleNodeIterator(SimpleNode root)
        { super(root); }

    protected SimpleNode getFirstChild(SimpleNode of)
        { return of.firstChild; }

    protected SimpleNode getNextSibling(SimpleNode of)
        { return of.nextSibling; }

    protected SimpleNode getParent(SimpleNode of)
        { return of.parent; }
}

And finally, at the bottom of our design, TreeIterator is a very reusable abstract base class that does the rest, now we've told it how to navigate our node class:

abstract class TreeIterator<TNode> implements Iterator<TNode>,
                                              Iterable<TNode>
{
    private TNode _next;

    protected TreeIterator(TNode root)
        { _next = root; }

    public Iterator<TNode> iterator()
        { return this; }

    public void remove()
        { throw new UnsupportedOperationException(); }

    public boolean hasNext()
        { return (_next != null); }

    public TNode next()
    {
        if (_next == null)
            throw new NoSuchElementException();

        TNode current = _next;

        _next = getFirstChild(current);

        for (TNode ancestor = current;
             (ancestor != null) && (_next == null);
             ancestor = getParent(ancestor))
        {
            _next = getNextSibling(ancestor);
        }

        return current;
    }

    protected abstract TNode getFirstChild(TNode of);
    protected abstract TNode getNextSibling(TNode of);
    protected abstract TNode getParent(TNode of);
}

(It's mildly naughty in that it implements Iterator and Iterable on the same object. This just means that you have to new up a fresh object in order to iterate a second time; don't try to reuse the same object).

This means that if your hierarchical structure consists of nodes for which you can define those three simple navigational operations, then all you have to do is derive your own equivalent of SimpleNodeIterator. This makes it very easy to enable this capability on any tree implementation.

If what you're iterating doesn't have a way to get the parent, you need to keep a stack during the iteration. Each time you descend a level, you push the state for the current level onto the stack. When you finish iterating at the current level, you pop the last state off the stack and continue with it. When the stack is empty, you're done. This means you have some intermediate storage, but its maximum size is proportional to the depth of the recursion rather than the number of items, so assuming the data is roughly balanced then it should be a lot more storage-efficient than copying all the items to a list before you return it.

Я обычно предпочитаю чтобы вернуть результат, поскольку я думаю, что

$result = extractPaths($arg,$arg2);

более понятен, чем

extractPaths($arg,$arg2,$result);

, но он полностью основан на вкусе.

Я бы выбрал вариант b, так как он создаст меньше объектов и, следовательно, будет более эффективным. Решение a больше похоже на то, как вы бы это сделали на функциональном языке, но оно основано на предположениях, которых нет в Java.

Если вы передадите объект, который нужно построить, если бы у вас было исключение, которое вы поймали в месте, где у вас была ссылка на этот объект, тогда у вас, по крайней мере, были бы данные, которые вы построили до тех пор, пока не было сгенерировано исключение.

Я лично передаю Builders в качестве аргументов, когда на нем будут «строиться» несколько методов, включая рекурсию. Таким образом, у вас будет только один строящийся объект, и вы потеряете много копий Set, Map или List.

в данном конкретном случае я предпочитаю последнее решение, так как:

1. оно позволяет избежать создания одноразовых коллекций
2. ваш алгоритм, реализованный таким образом, не может получить никакой выгоды от "функциональности"

imho нет реальной пользы от функциональности без действительно веской причины f (например, использования потоков).

передать коллекцию в качестве параметра для этого метода

Позже будет создано меньше объектов в памяти (поскольку уже сказано), но также управляет каждым путем в дереве только один раз: при извлечении и сохранении в результате Set он не добавляется к любому другому набору снова, снова и снова.