如何进行递归搜索？

Question

我有一个Task类,它可以有相同类型的子任务

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

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

你需要三件事来做递归工作:

• 每次递归时问题都必须变小.
• 问题必须最终变得如此之小,以至于它可以在没有递归的情况下得到解决
• 问题必须通过将其分解为一系列较小的问题,解决每个问题并将结果组合来解决.

如果你不能保证这三件事,那么就不要使用递归解决方案.

Answer 2

你是对的,递归是正确的方法.这样的事情应该有效:

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)