Как выполнить рекурсивный поиск?

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

Решение Свика в порядке, но я подумал, что добавлю немного более общих советов.Похоже, вы новичок в написании рекурсивных методов и немного боролись там.Самый простой способ написать рекурсивный метод - строго следовать шаблону:

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)

Answer 3

Отделение итерации по дереву от поиска может быть полезным, если есть другие задачи, которые вы хотите выполнить для всех элементов.Т.е., если вы реализуете IEnumerable над элементами дерева, вы можете использовать LINQ-запросы для поиска всего, что вы хотите, или выполнять другие операции над всеми задачами в вашем дереве.Проверьте Реализация IEnumerable в древовидной структуре , чтобы узнать, как это сделать.