如何執行遞歸搜索？

Question

我可以有相同的類型

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

我應該如何執行遞歸搜索（LINQ也許）找到與最早開始日期的任務的子任務的任務類？

我最初的做法涉及太多的循環，它結束變得有點混亂，並迅速螺旋失控。這是我的第二次嘗試：

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; 
} 

任何更好的解決方案，那裏解決這個問題？

感謝

Answer 1

你說得對，遞歸這裏是正確的做法。像這樣的東西應該工作：

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; 
} 

我刪除了檢查爲task.HasSubTasks()，因爲它只是使代碼更復雜，沒有任何額外的好處。

如果您發現自己經常編寫需要遍歷樹中所有任務的代碼，那麼您可能希望使其更通用。例如，您可以有一個返回IEnumerable<Task>的方法，該方法返回樹中的所有任務。然後找到最小的開始日期將是一樣容易：

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

Answer 2

分離遍歷所有樹的搜索，如果有你想上的所有項目執行其他任務，可能是有益的。即如果您通過樹項目實現IEnumerable，則可以使用LINQ查詢來搜索任何您想要的內容或對您樹中的所有任務執行其他操作。 檢查出Implementing IEnumerable on a tree structure的方式來做到這一點。

Answer 3

Svick的解決方案很好，但我想我會添加一些更一般的建議。看起來你是寫新遞歸方法的新手，並且在那裏掙扎了一下。寫一個遞歸方法最簡單的辦法就是嚴格遵循一個模式：

Result M(Problem prob) 
{ 
    if (<problem can be solved easily>) 
     return <easy solution>; 
    // The problem cannot be solved easily. 
    Problem smaller1 = <reduce problem to smaller problem> 
    Result result1 = M(smaller1); 
    Problem smaller2 = <reduce problem to smaller problem> 
    Result result2 = M(smaller2); 
    ... 
    Result finalResult = <combine all results of smaller problem to solve large problem> 
    return finalResult; 
} 

因此，假設你要解決的問題「什麼是我的二叉樹的最大深度是多少？」

int Depth(Tree tree) 
{ 
    // Start with the trivial 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; 
} 

您需要三樣東西，使遞歸工作：

• 這個問題有小你遞歸每一次得到的。
• 問題必須最終變得很小以至於無需遞歸即可解決
• 該問題必須通過將問題分解爲一系列較小的問題，解決每個問題併合並結果來解決。

如果不能保證這三樣東西，然後不使用遞歸解決方案。