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:

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:

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.

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:

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)

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?)