Y Combinator para C# – Recursão pero no mucho

Depois de mais de um ano sem escrever nada, tenho a nobre intensão de escrever ao menos dois ou três posts até o final do ano. Apenas para esquentar, vou começar com este onde gostaria de abordar uma técnica que nasceu para linguagens funcionais e que, cada vez mais, venho encontrando motivos e utilidade na utilização dela em meu cotidiano programando c#.

Este artigo é praticamente um Ode a este do Matt Might e aborda uma técnica chamada Y combinator (aqui focando em C#). Detalhes sobre a história por trás do conceito podem ser encontrados aqui ou diretamente no artigo do cara (que vale muito a leitura).

Em poucas palavras, a idéia aqui é transformar a recursão em uma forma alternativa de execução da função F encapsulada em um template que a expõe (dificultei?).

A ideia é bem simples, a implementação acaba dando uma leve sensação de brain fuck quando visto pela primeira vez – normal. Com código geralmente as coisas ficam mais fáceis…

Fibonacci

Ok, fibonacci é um bom exemplo de onde usar recursão de modo eficiente pode ser útil – ou, não usar recursão at all ¹.

Abaixo um código simples para resolver Fibonacci em C# usando recursão:

private static long FibonacciSimples(long n)
 {
    return n < 2 ? n : (FibonacciSimples(n - 1) + FibonacciSimples(n - 2));
 }

O resultado para FibonacciSimples(150) é (ou seria): “9969216677189303386214405760200” ou “9 nonillion 969 octillion 216 septillion 677 sextillion 189 quintillion 303 quadrillion 386 trillion 214 billion 405 million 760 thousand 200” (com os cumprimentos do wolframalpha).

Com esta informação em mãos já dá pra ter uma ideia da quantidade de computação acontecendo em uma chamada com um valor que não é tão grande, certo? Em alguns casos, dependendo do grau de recursão necessário para obter o resultado, a chance é de que você veja uma imagem parecida com seguinte:

Overfuck

A opção aqui é fazer uso do Y combinator e realizar as chamadas de forma “contínua” dentro do template do algoritmo. Isto não obrigatoriamente elimina a recursão, mas no nosso caso, o desvio na stack é visível. Novamente, com código as coisas ficam mais simples de se entender, então aqui vamos nós em direção ao Y em C#:

   public static Func<long, long> Y(Func<Func<long, long>, Func<long, long>> f)
   {
      Func<Func<dynamic, Func<decimal, decimal>>, Func<decimal, decimal>> _ = x => f(x1 => x(x)(x1));
      return _(x => f(y => x(x)(y)));
   }

E, nosso código para obter o Fibonacci deve sofrer algumas alterações para suportar o novo modelo:

   public static Func<decimal, decimal> FibonaccY(Func<decimal, decimal> f)
   {
      return n =>
      {
         return n < 2 ? n : (f(n - 1) + f(n - 2));
      };
   }

A diferença, no que tange a recursão, pode ser mais facilmente visualizada no grafo a seguir (gerado com o CodeMap) – note que apesar das chamadas sempre rotearem entre os 3 métodos que são parte do ciclo de calculo de Fibonacci, existe um label “External Code” junto a chamada do “AnonymousMethod__c”.

Recursão

(Cache it) => Memoization

Agora, como um bônus para nosso projeto, que tal dar uma dinamizada na obtenção do resultado? Neste ponto com o que sabemos isto não tende a ser difícil. Abaixo criamos um método que encapsula a execução do FibonaccY e executa os calculo usando o dicionário de cache que fornecermos/incrementamos:

      public static Func<decimal, decimal> YCache(Func<Func<decimal, decimal>, Func<decimal, decimal>> f, Dictionary<decimal, decimal> cache = null)
      {
            if (cache == null) { cache = new Dictionary<decimal, decimal>(); }
            return i =>
            {
                decimal result;
                if (!cache.TryGetValue(i, out result))
                {
                    var r = f(n => YCache(f, cache)(n))(i);
                    cache.Add(i, result = r);
                }
                return result;
            };
      }

Fonte completo

O fonte completo deste artigo pode ser baixado diretamente no Gist.

Curiosidades

  1. E se abandonarmos completamente o pensamento recursivo? Também conhecido como Binet’s Formula.
  2. Um vídeo sobre Y combinator
  3. Uma discussão muito interessante sobre o tema na HN
  4. Existem algumas referências de Y para C# na web. Algumas bem legais, outras nem tanto. Uma das que eu mais gosto é esta aqui.
    1. Uma diferença sutil mas importante, o CodeMap para o modelo de execução descrito no artigo da MSDN é o seguinte:

recursao

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: