Comment effectuer une recherche récursive?

J’ai une classe de tâches qui peut avoir des sous tâches du même type

public class Task { public DateTime Start { get; set;} public DateTime Finish { get; set;} public List Tasks {get; set;} public DateTime FindTaskStartDate(Task task) {} }

Comment dois-je effectuer une recherche récursive (linq peut-être) pour trouver la tâche avec la date de début la plus proche?

Mon approche initiale impliquait un trop grand nombre de boucles et cela a fini par devenir un désordre et une spirale incontrôlable. Voici ma deuxième tentative:

 public DateTime FindTaskStartDate(Task task) { DateTime startDate = task.Start; if(task.HasSubTasks()) { foreach (var t in task.Tasks) { if (t.Start < startDate) { startDate = t.Start; if (t.HasSubTasks()) { //What next? //FindTaskStartDate(t); } } } } return startDate; }

Des solutions plus agréables pour résoudre ce problème?

Merci

Vous avez raison, la récursivité est la bonne approche ici. Quelque chose comme ça devrait marcher:

 public DateTime FindTaskStartDate(Task task) { DateTime startDate = task.Start; foreach (var t in task.Tasks) { var subTaskDate = FindTaskStartDate(t); if (subTaskDate < startDate) startDate = subTaskDate; } return startDate; }

J'ai supprimé la vérification de task.HasSubTasks() , car cela ne fait que rendre le code plus compliqué sans aucun avantage supplémentaire.

Si vous trouvez que le code que vous écrivez souvent nécessite de parcourir toutes les tâches de l'arborescence, vous souhaiterez peut-être rendre cela plus général. Par exemple, vous pourriez avoir une méthode qui renvoie IEnumerable qui renvoie toutes les tâches de l’arborescence. Trouver la plus petite date de début serait alors aussi simple que:

 IterateSubTasks(task).Min(t => t.Start)

La solution de Svick est bonne, mais j’ai pensé append un conseil plus général. Il semble que vous débutiez dans l’écriture de méthodes récursives et que vous vous débattiez un peu là-bas. Le moyen le plus simple d’écrire une méthode récursive est de suivre ssortingctement un modèle:

 Result M(Problem prob) { if () return ; // The problem cannot be solved easily. Problem smaller1 =  Result result1 = M(smaller1); Problem smaller2 =  Result result2 = M(smaller2); ... Result finalResult =  return finalResult; }

Supposons donc que vous souhaitiez résoudre le problème “quelle est la profondeur maximale de mon arbre binary?”

 int Depth(Tree tree) { // Start with the sortingvial case. Is the tree empty? if (tree.IsEmpty) return 0; // The tree is not empty. // Reduce the problem to two smaller problems and solve them: int depthLeft = Depth(tree.Left); int depthRight = Depth(tree.Right); // Now combine the two solutions to solve the larger problem. return Math.Max(depthLeft, depthRight) + 1; }

Trois choses sont nécessaires pour que la récursivité fonctionne:

Le problème doit être réduit à chaque fois que vous recurse.
Le problème doit finalement devenir si petit qu’il peut être résolu sans récursivité
Le problème doit pouvoir être résolu en le décomposant en une série de problèmes plus petits, en résolvant chacun d’entre eux et en combinant les résultats.

Si vous ne pouvez pas garantir ces trois choses, n’utilisez pas de solution récursive .

Séparer itération de l’arborescence de la recherche peut être utile si vous souhaitez effectuer d’autres tâches sur tous les éléments. En d’autres termes, si vous implémentez IEnumerable sur les éléments de l’arborescence, vous pouvez utiliser les requêtes LINQ pour rechercher tout ce que vous voulez ou effectuer d’autres opérations sur toutes les tâches de votre arborescence. Consultez Implémentation de IEnumerable dans une arborescence pour savoir comment procéder.