Обработка общих рекурсивных функций

Question

Я заметил, что в моем проекте мы часто пишем рекурсивные функции.

У меня вопрос: есть ли способ создать рекурсивную функцию как универсальную функцию для каждой иерархической структуры, которая использует рекурсивную итерацию?

Может быть, я могу использовать делегата, который получает корень и флаг завершения рекурсии?

Есть идеи?

Спасибо.

Answer 1

У меня вопрос: есть ли способ создать рекурсивную функцию как универсальную функцию для каждой иерархической структуры, которая использует рекурсивную итерацию? Может быть, я могу использовать делегат, который получает корень и конечный флаг рекурсивного?

Да. Единственное, что вам нужно, это функция-делегат, которая вычисляет список дочерних элементов для каждого элемента. Функция завершается, когда дочерние элементы не возвращаются.

    delegate IEnumerable<TNode> ChildSelector<TNode>(TNode Root);

    static IEnumerable<TNode> Traverse<TNode>(this TNode Root, ChildSelector<TNode> Children) {
        // Visit current node (PreOrder)
        yield return Root;

        // Visit children
        foreach (var Child in Children(Root)) 
            foreach (var el in Traverse(Child, Children))
                yield return el;

    }

Пример:

        static void Main(string[] args) {

        var Init = // Some path

        var Data = Init.Traverse(Dir => Directory.GetDirectories(Dir, "*", SearchOption.TopDirectoryOnly));

        foreach (var Dir in Data)
            Console.WriteLine(Dir);

        Console.ReadKey();
    }

Answer 2

Я думаю, что вам нужен способ работы с иерархическими структурами универсальным способом («универсальным», как определено на английском языке, не обязательно, как определено в .Net). Например, это то, что я написал однажды, когда мне нужно было получить все элементы управления внутри формы Windows:

public static IEnumerable<T> SelectManyRecursive<T>(this IEnumerable<T> items, Func<T, IEnumerable<T>> selector)
{
    if (items == null)
        throw new ArgumentNullException("items");
    if (selector == null)
        throw new ArgumentNullException("selector");

    return SelectManyRecursiveInternal(items, selector);
}

private static IEnumerable<T> SelectManyRecursiveInternal<T>(this IEnumerable<T> items, Func<T, IEnumerable<T>> selector)
{
    foreach (T item in items)
    {
        yield return item;
        IEnumerable<T> subitems = selector(item);

        if (subitems != null)
        {
            foreach (T subitem in subitems.SelectManyRecursive(selector))
                yield return subitem;
        }
    }
}


// sample use, get Text from some TextBoxes in the form
var strings = form.Controls
                  .SelectManyRecursive(c => c.Controls) // all controls
                  .OfType<TextBox>() // filter by type
                  .Where(c => c.Text.StartWith("P")) // filter by text
                  .Select(c => c.Text);

Другой пример: класс Category, где у каждого Category может быть ChildCategories (так же, как у Control есть коллекция Controls) и предполагается, что rootCategory является прямым или косвенным родителем всех категорий :

// get all categories that are enabled
var categories = from c in rootCategory.SelectManyRecursive(c => c.ChildCategories)
                 where c.Enabled
                 select c;

Answer 3

Более простой и общий подход может заключаться в кэшировании результатов функции и использовании «реальной» функции только тогда, когда результат известен - эффективность этого подхода зависит от того, как часто один и тот же набор параметров используется во время рекурсии. .

Если вы знаете Perl, вам следует проверить первые 4 главы Perl высшего порядка , которые доступны в виде электронной книги, представленные идеи не зависят от языка.

Answer 4

Похоже, ваше решение может успешно использовать Шаблон посетителя .

Вы можете создать конкретный вариант шаблона посетителя , создав иерархический шаблон посетителя .

Это немного сложно обсудить полностью здесь, но это должно помочь вам начать некоторые исследования. Основная идея заключается в том, что у вас есть класс, который знает, как обходить структуру, а затем у вас есть классы Visitor, которые знают, как обрабатывать определенный узел. Вы можете отделить обход дерева с обработкой узлов.

Answer 5

Я не уверен, о чем конкретно просит ваш вопрос, но рекурсивная функция может быть универсальной. Там нет никаких ограничений на это. Например:

int CountLinkedListNodes<T>(MyLinkedList<T> input) {
   if (input == null) return 0;
   return 1 + CountLinkedListNodes<T>(input.Next);
}