Рекурсивный метод: параметр одного элемента или набор элементов?

Question

У меня есть вопрос о достоинствах двух разных подходов к реализации рекурсивного метода. Я всегда следовал подходу версии 1, то есть принимал один параметр Node, но недавно я столкнулся со стилем, используемым в версии 2, который принимает набор узлов.

Рассмотрим следующий класс Node вместе с двумя версиями метода Visit:

class Node
{
    public List<Node> children = new List<Node>();
    // other data members 
}

Версия 1 принимает один параметр узла:

Visit(Node n)
{
  DoSomethingUsefulWith(n);

  foreach (Node child in n.children)
    Visit(child);
}

Версия 2 принимает набор узлов:

Visit(List<Node> nodes)
{
  foreach (Node n in nodes)
  {
    DoSomethingUsefulWith(n);
    Visit(n.children);
  }
}

Есть ли какие-либо преимущества, даже стилистически, в использовании одной формы над другой? Должен ли выбор основываться исключительно на том, начинаете ли вы с одного узла по сравнению с набором узлов, хотя было бы тривиально использовать версию любого метода в любом случае?

Answer 1

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

Answer 2

Я бы не реализовал версию 2, всегда версию 1.
Версия 2 в основном является версией 1 в цикле for-each

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

Я не думаю, что производительность здесь является реальной проблемой. Оба метода имеют один (по ссылке) аргумент, они должны использовать примерно одинаковый объем памяти.

Однако .NET может оптимизировать один из двух вариантов немного лучше. Профилируйте оба метода, чтобы быть уверенным.

Answer 3

Лично я считаю, что версия 1 лучше отражает рекурсивное определение дерева (которое обычно основано на одном узле). Поэтому я бы предпочел версию 1.

Answer 4

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

Imo, версию 1 гораздо проще читать, поэтому я бы выбрал номер I.

Answer 5

Единственное существенное отличие, которое я вижу, заключается в простоте звонка.

Как насчет этой версии 3:

void Visit(Node n)
{
    DoSomethingUsefulWith(n);
    Visit(n.children);
}

void Visit(List<Node> nodes)
{
    foreach (Node n in nodes)
        Visit(n);
}

Answer 6

Вы должны передавать как можно меньше параметров в своих рекурсивных функциях (даже относительно размера памяти, выделенной для используемого вами типа).Это общее правило, которому я следую.Если вы передадите несколько больших структур, вам может не хватить памяти.Если вы используете ссылочный тип, это не проблема.

Answer 7

Стилистически это зависит от корня типа объекта, который вы повторяете.

Фактически они одинаковы. если мой мозг не в парке .....