Recursão, recursion, ricorsione, αναδρομή, …

Dentro da Teoria da Computação, um programa pode ser categorizado de acordo com 3 tipos de estruturação: monolítica, iterativa e recursiva.

Fazendo uma analogia com alguma linguagem de programação posso associar a estruturação monolítica ao BASIC que programava quando garoto caracterizado pelo seus desvios incondicionais (vulgo GOTOs e GOSUBs – eu ainda lembro disto, uau!) e estruturação iterativa – populares em linguagens estruturadas, como por exemplo Pascal, e muito forte por banir os desvios incondicionais por serem considerados grosseiros, rídiculos, perigosos, vai dar m… No entanto, isto é teoria, pois na prática todas as (ou a maioria das) linguagens de programação(bem, pelo menos as que eu escolhi para programar) suportam estruturação recursiva, ou seja, suportam recursividade. Alias, isto é um négocio tão simples que “para você entender de recursividade, basta você entender de recursividade”, sacou? Não? Então novamente: “para você entender de recursividade, basta você entender de recursividade” – agora sim!

Baseado num famoso trecho de Orwell, posso dizer: “… que algumas linguagens são mais recursivas do que outras”.

A maioria dos programadores que conheço sabem ou já ouviram falar sobre recursividade. Mas se você perguntar o que é, provavelmente a resposta seria: “Ah, é uma função que chama a si própria”. Ok! Este é um tipo: a função recursiva. O outro é a estrutura de dados recursiva: o nó de uma lista ligada (Linked List) ou de uma árvore (Tree), a enumeração de dirétorios e arquivos ou de janelas.

Recursividade é tão importante que é um dos pilares das Linguagens Funcionais e um recurso fundamental para a Matemática. Por exemplo, o algoritmo babilônico para a computação do lado do quadrado (square root) é definido recursivamente por:

image

O “sr” na função representa um chute (guess), você calculará inúmeras (“n”) vezes até chegar num resultado coerente dentro de “k” casas decimais para o valor de “x” – você perceberá que esta coerência surgirá quando uma execução sucessiva produzirá resultados semelhantes ou muito, mas muito, próximos. Let’s try:

image

Note que no Mathematica, o algoritmo está um pouco modificado em relação ao apresentado.

Interessante isto, não é mesmo? Tão interessante quanto, é saber que é possível representar estruturas de controle, tais como for ou while, em termos recursivos.

image

No exemplo, escrito em Scala, a função recursiva While é uma função tail recursive. Resumidamente, isto significa que o compilador ou máquina virtual (ou ambos) conseguem otimizar a chamada e não sobrecarregar a call stack.

Imagine por um momento, que surgisse uma vontade incontrolável de implementar um código para gerar séries harmonicas em C++. E falaram para você que este tal de C++ suporta Orientação a Objetos. Juntamente com esta vontade te consumindo, você também ouviu falar num cara chamado Template Method Pattern. Decidido a misturar tudo isto e ver o que pode dar, escreveu o seguinte código, que por sinal usa chamadas recursivas e é compilado com a máaaaaaxima otimização possível:

image

Apesar de eu não ter te explicado, você percebeu que o método SummationCore da classe Harmonic é implementado totalmente segundo os principios de comandam uma boa função tail recursive. O problema é que você caiu numa armadilha do C++.

O fato é: o método é virtual, ele necessita ser resolvido em tempo de execução, então o C++ (pelo menos o cl.exe [Microsoft (R) C/C++ Optimizing Compiler Version 16.00.40219.01], digo o compilador do Visual C++ 10) não pode otimizar agressivamente este código. Note a quantidade de chamadas na Call Stack!

Para concertar este problema, sem alterar a estrutura do código ou usar templates, como regra básica assuma: toda vez que um método virtual for resolvido como tail recursive, implemente-o em termos de outro método não virtual. Assim, o compilador poderá produzir um resultado otimizado! (E este resultado é exatamente resolvido através de desvios – JMPs ou GOTOs, mas esta é uma outra estória)

image

A versão tail recursive em C++, na integra:

#include <cstdio>

struct Serie
{
    virtual ~Serie(){}

    float Summation(int n)
    {
        return SummationCore(n);
    }

protected:
    virtual float SummationCore(int n) = 0;
};

struct Harmonic : public Serie
{
    Harmonic() : Acc_(0){}

protected:
    virtual float SummationCore(int n)
    {
        return TailRecursiveSummation(n);
    }

    float TailRecursiveSummation(int n)
    {
        if(n == 1)
            return Acc_;

        Acc_ += 1.0 / n;

        return TailRecursiveSummation(n - 1);
    }

private:
    float Acc_;
};

int main()
{
    std::printf( "%f", Harmonic().Summation(7) );
}

Não esqueça de olhar a Call Stack (impressionante, não acha?)

About Fabio Galuppo

I'm Software Engineer and Professional Trainer. I love Programming and Rock'n'Roll.
This entry was posted in C++, Functional Programming, Math. Bookmark the permalink.

4 Responses to Recursão, recursion, ricorsione, αναδρομή, …

  1. jumpi says:

    Excelente!!! Colocarei o seu blog na minha RSS…🙂

    A propósito, viu o mail que te mandei??? Abraços ai brother!!!😀

  2. Muito bom, meu amigo. Que bom que você voltou a escrever.
    Só ficou faltando explicar porque o método virtual não pode ser otimizado (porque ele precisa ser resolvido em tempo de execução via VTable).
    E eu não conhecia o Wolfram Mathematica. Tem versão NFR pra MVPS?🙂

    • fabiogaluppo says:

      Curioso este comentário. Pq exatamente qdo eu recebi este seu comment, eu estava tirando o print-screen de uma vtable – que aliás o final deste post é gancho do próximo…🙂

      A escolha dos assuntos recursão (tail recursive) e virtual members é inspirado numa passagem que mostrei rapidamente e comentei no TechEd 2011 com Actors (Agents Library do Visual C++) e C++, você deve lembrar, não? Então achei que merecia tal registro.

      Sobre o Mathematica, que aliás é um software animal, é uma pena que não há uma versão free. Mas, a Home Edition é bem acessivel e da para explorar vários recursos, recomendo!

  3. Pingback: Retrospectiva 2012 | C++ Renaissance & Functional Revolution

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s