Manipulação recursiva funções comuns

votos
1

Tenho notado que no meu projeto, que frequentemente está escrevendo funções recursivas.

A minha pergunta é: existe alguma maneira de criar a função recursiva como função genérica para cada estrutura de hierarquia que está usando a iteração recursiva?

Talvez eu possa usar um delegado que recebe a raiz ea bandeira final da recursão?

Alguma ideia?

Obrigado.

Publicado 19/05/2009 em 15:38
fonte usuário
Em outras línguas...                            


5 respostas

votos
1

A minha pergunta é: existe alguma maneira de criar a função recursiva como função genérica para cada estrutura de hierarquia que está usando a iteração recusive? pode ser que eu posso usar um delegado que recebe a raiz ea bandeira final do recursiva?

Sim - A única coisa que você precisa é uma função de delegado que calcula uma lista de crianças para cada elemento. A função termina quando há crianças são devolvidos.

    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;

    }

Exemplo:

        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();
    }
Respondeu 19/05/2009 em 16:15
fonte usuário

votos
1

Acho que o que você quer é uma maneira de trabalhar com estruturas hierárquicas de uma forma genérica ( "genérico", como definido em Inglês, não necessariamente como definido na Net). Por exemplo, isso é algo que eu escrevi uma vez, quando eu precisava para obter todos os controles dentro de um formulário do 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);

Outro exemplo: a Categoryclasse onde cada um Categorypoderia ter ChildCategories(mesma forma que um Controltem uma Controlscoleção) e assumindo que rootCategoryé direta ou indiretamente, o pai de todas as categorias:

// get all categories that are enabled
var categories = from c in rootCategory.SelectManyRecursive(c => c.ChildCategories)
                 where c.Enabled
                 select c;
Respondeu 19/05/2009 em 16:05
fonte usuário

votos
0

Parece que sua solução pode usar com sucesso o padrão do visitante .

Você pode criar uma variação específica do padrão do visitante , criando um padrão do visitante hierárquica .

É um pouco complexo para discutir inteiramente aqui, mas que deve começar em algumas pesquisas. A idéia básica é que você tem uma classe que sabe como atravessar a estrutura, e então você tem aulas de visitantes que sabem como processar um nó particular. Você pode separar o percurso da árvore com o processamento de nós.

Respondeu 19/05/2009 em 16:03
fonte usuário

votos
0

Uma abordagem mais fácil e também genérica poderia ser a de armazenar em cache os resultados da função e usar a função "real" somente quando o resultado é conhecido - a eficácia da presente abordagem depende de como frequentemente o mesmo conjunto de parâmetros é usado durante a sua recursividade.

Se você sabe Perl você deve verificar os 4 primeiros capítulos da mais alta ordem Perl que estão disponíveis como um ebook, as idéias apresentadas são independentes do idioma.

Respondeu 19/05/2009 em 15:55
fonte usuário

votos
0

Eu não tenho certeza do que exatamente a sua pergunta está pedindo, mas uma função recursiva pode ser genérica. Não há nenhuma limitação sobre isso. Por exemplo:

int CountLinkedListNodes<T>(MyLinkedList<T> input) {
   if (input == null) return 0;
   return 1 + CountLinkedListNodes<T>(input.Next);
}
Respondeu 19/05/2009 em 15:42
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more