Méthode récursive: paramètre d'élément unique ou collection d'éléments?

Question

J'ai une question sur les mérites de deux approches différentes pour mettre en œuvre une méthode récursive. J'ai toujours suivi l'approche de la version 1, c'est-à-dire en acceptant un seul paramètre Node, mais j'ai récemment rencontré le style utilisé dans la version 2, qui accepte une collection de nœuds.

Tenir compte de la classe de noeud suivant, ainsi que les 2 versions de la méthode de visite:

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

Version 1 accepte un seul paramètre Node:

Visit(Node n) 
{ 
    DoSomethingUsefulWith(n); 

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

Version 2 accepte une collection de nœuds:

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

Y a-t-il des avantages, même stylistiques, à utiliser une forme sur la autre? Le choix devrait-il être basé uniquement sur le fait de savoir si vous commencez avec un seul nœud par rapport à une collection de nœuds, même s'il serait trivial d'utiliser l'une ou l'autre version de la méthode dans les deux cas?

Answer 1

je ne voudrais pas mettre en œuvre la version 2, toujours la version 1.
version 2 est essentiellement la version 1 dans une boucle for-each

Si vous décidez plus tard que vous voulez appeler la méthode avec un paramètre, vous pouvez toujours réutiliser la version 1.
Si vous n'avez que la version 2 et un nœud, vous devez créer une liste fictive pour utiliser la version 1.

Je ne sais pas pense que la performance est un vrai problème ici. Les deux méthodes ont un argument (par référence), ils devraient utiliser à peu près la même quantité de mémoire.

Toutefois, .NET pourrait être en mesure d'optimiser l'un des deux un peu mieux. Profil les deux méthodes pour être sûr.

Answer 2

Vous devriez transmettre le moins possible de paramètres dans vos fonctions de récurrence (même en ce qui concerne la taille de la mémoire dédiée au type que vous utilisez). C'est la règle générale que je suis. Si vous passez de grandes structures, vous pouvez manquer de mémoire. Si vous utilisez un type de référence, ce n'est pas un problème.

Answer 3

La seule différence significative que je peux voir est dans la facilité d'appel.

Que diriez-vous cette version 3:

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

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

Answer 4

Stylistiquement cela dépend de la racine du type d'objet que vous récursion.

Effectivement, ils sont identiques. à moins que mon cerveau est dans le parc .....

Answer 5

Je pense qu'il n'y a pas vraiment de bénéfice pour la version 2 - seulement que cela limite la flexibilité de votre fonction, puisque vous ne pouvez plus démarrer votre récursivité avec un seul nœud.

Imo, version 1 est beaucoup plus facile à lire, donc je pencherais pour le numéro I.

Answer 6

Je préfère la signature qui prend un seul nœud puisque je n'ai pas alors de construire une liste artificielle si je ne vouloir faire l'opération sur ce noeud et c'est les enfants. C'est aussi facile à utiliser sur une liste de nœuds que de simplement parcourir la liste et l'appliquer à chacun.

Answer 7

Personnellement, je pense que la version 1 reflète mieux la définition récursive d'un arbre (qui est généralement basé sur un seul noeud). Par conséquent je favoriserais la version 1.