Recursividade

Uma forma visual de recursão conhecida como efeito Droste.

'Recursividade' é um termo usado de maneira mais geral para descrever o processo de repetição de um objeto de um jeito similar ao que já fora mostrado. Um bom exemplo disso são as imagens repetidas que aparecem quando dois espelhos são apontados um para o outro.

Definição formal

Na matemática e na ciência da computação, a recursão especifica (ou constrói) uma classe de objetos ou métodos (ou um objeto de uma certa classe) definindo alguns poucos casos base ou métodos muito simples (frequentemente apenas um), e então definindo regras para formular casos complexos em termos de casos mais simples.

Por exemplo, segue uma definição recursiva da ancestralidade de uma pessoa:

Os pais de uma pessoa são seus antepassados (caso base);
Os pais de qualquer antepassado são também antepassados da pessoa em consideração (passo recursivo).

É conveniente pensar que uma definição recursiva define objetos em termos de objetos “previamente definidos” dessa mesma classe que está sendo definida.

Definições como esta são frequentemente encontradas na matemática, por exemplo, a definição formal dos números naturais diz que 0 (zero) é um número natural, e todo número natural tem um sucessor, que é também um número natural.

Recursão na linguagem

O uso mais antigo de recursão na linguística, e o uso da recursão em geral, remete ao linguista Pāṇini em meados de 500 AC, o qual fez uso da recursão nas regras gramaticais do Sânscrito (língua clássica da Índia antiga que influenciou praticamente todos os idiomas ocidentais).

O linguista Noam Chomsky lançou a teoria de que a extensão ilimitada de uma língua natural é possível apenas pelo mecanismo recursivo de encaixar frases em frases. Assim, uma garotinha tagarela pode muito bem dizer, "Dorothy, que encontrou a Bruxa Má do Oeste na Terra dos Munchkins, onde a bruxa má da sua irmã foi morta, liquidou-a com um balde de água.” Claramente, duas frases simples — "Dorothy encontrou a Bruxa Má do Oeste na Terra dos Munchkins" e "Sua irmã foi morta na Terra dos Munchkins" — podem ser encaixadas em uma terceira frase, "Dorothy liquidou-a com um balde de água", para obter uma frase exacerbadamente prolixa.

Aqui está uma outra maneira, possivelmente mais simples, de se entender processos recursivos:

Nós já terminamos? Se sim, retorne os resultados. Sem uma condição de parada como esta, uma recursão iria se repetir eternamente.
Se não, simplifique o problema, resolva o(s) problema(s) mais simples, e então encaixe os resultados na solução do problema original. Então retorne a solução.

Aqui vai uma ilustração mais humorística: "Para entender a recursão, a pessoa deve primeiro entender a recursão." Ou talvez seja mais adequado o exemplo seguinte criado por Andrew Plotkin: "Se você já sabe o que é a recursão, apenas se lembre da resposta. Caso contrário, encontre alguém que esteja mais próximo de Douglas Hofstadter do que você; então pergunte a ele ou a ela o que é a recursão."

Exemplos de objetos matemáticos frequentemente definidos recursivamente são funções, conjuntos, e especialmente fractais.

A recursão em português claro

A recursão é o processo pelo qual passa um certo procedimento quando um dos passos do procedimento em questão envolve a repetição completa deste mesmo procedimento. Um procedimento que se utiliza da recursão é dito recursivo. Também é dito recursivo qualquer objeto que seja resultado de um procedimento recursivo.

Para entendermos a recursão, devemos primeiro compreender a diferença entre um procedimento e a execução de um procedimento. Um procedimento é um conjunto de passos que devem ser tomados baseados em um conjunto de regras. A execução de um procedimento envolve seguir de fato as regras e executar os passos. Uma analogia para isso é que um procedimento é como uma ementa (cardápio) que nos fornece as opções possíveis, enquanto a execução de um procedimento é escolhermos de fato qual refeição nos será servida.

Um procedimento é dito recursivo quando um de seus passos consiste na chamada de uma nova execução do procedimento. Consequentemente, uma refeição recursiva com quatro pratos seria uma refeição em que a entrada, a salada, o prato principal ou a sobremesa por si próprios já consistissem em refeições. Então uma refeição recursiva poderia ser feita por purês de batata, salada verde, frango grelhado, e para sobremesa, uma refeição de quatro pratos com bolinhos de bacalhau, salada de legumes, como prato principal uma refeição de quatro pratos, e para sobremesa um pedaço de bolo de chocolate, e assim sucessivamente até que a refeição esteja completa.

Um procedimento recursivo deve completar cada um de seus passos. Mesmo se uma nova chamada é feita, cada execução deve passar por cada um dos passos restantes. O que isso quer dizer é que, mesmo a salada sendo ela própria uma refeição inteira de quatro pratos, você ainda deverá comer o prato principal e a sobremesa.

Humor recursivo

Uma piada comum de nerd (por exemplo, [1]) é a seguinte “definição” de recursão.

Recursão

Ver "Recursividade".

Isso é uma paródia às referências encontradas em dicionários, que em alguns casos podem levar a definições circulares. Toda piada tem um elemento de sabedoria e também um elemento de mal-entendido. Esse é também o segundo menor exemplo de definição errônea de recursão de um objeto: o erro começa pela ausência de uma condição de parada (ou falta de um estado inicial, se visto por outro ponto de vista). Iniciantes em recursão ficam frequentemente confusos pela sua aparente circularidade, até que eles compreendem que a condição de término é fundamental. Uma versão mais correta seria:

Recursão

Se você ainda não entendeu; Ver: "Recursividade".

Outros exemplos são os acrônimos recursivos, tais como GNU, PHP ou OPO (Dilbert; "O Projeto OPO").

Outra forma de humor recursivo é frequentemente encontrada em filmes e animações, tal como este exemplo [2].

Recursão na matemática

O triângulo de Sierpinski —uma recursão fechada de triângulos formando uma reticulada geométrica.

Conjuntos definidos recursivamente

Exemplo: os números naturais.

Um exemplo de conjunto definido recursivamente é dado pelos números naturais:

0 está em N;

Se n está em N, então n + 1 está em N.

O conjunto dos números naturais é o menor conjunto satisfazendo as condições acima.

Exemplo: o conjunto das proposições verdadeiras alcançáveis

Outro exemplo interessante é o conjunto das proposições verdadeiras alcançáveis em um sistema axiomático.

Se uma proposição é um axioma, ela é uma proposição verdadeira alcançável.
Se uma proposição pode ser obtida de proposições verdadeiras alcançáveis por meio de regras de inferência, ela é uma proposição verdadeira alcançável.
O conjunto das proposições verdadeiras alcançáveis é o menor conjunto de proposições verdadeiras satisfazendo estas condições.

Esse conjunto é chamado 'proposições verdadeiras alcançáveis' porque: em aproximações não-construtivas aos fundamentos da matemática, o conjunto das proposições verdadeiras é maior que o conjunto recursivamente construído a partir de axiomas e regras de inferência. Ver também teorema da incompletude de Gödel.

(Note que determinar se um certo objeto está ou não em um conjunto definido recursivamente não é uma tarefa algorítmica.)

Recursão funcional

Uma função pode ser parcialmente definida em termos de si mesma. Um exemplo conhecido é a Sequência de Fibonacci: F(n) = F(n − 1) + F(n − 2). Para que tal definição seja útil, ela deve convergir para valores que não sejam recursivamente definidos, nesse caso F(0) = 0 e F(1) = 1.

Uma função recursiva famosa é a função de Ackermann que, ao contrário da sequência de Fibonacci, é bem difícil de ser expressa sem o uso da recursão.

Demonstrações recursivas

A maneira padrão de se definir novos sistemas de matemática ou lógica é definindo objetos (tais como “verdadeiro” e “falso”, ou “todos os números naturais”), e então definindo operações sobre eles. Esses são os casos base. Após isso, todas as computações válidas no sistema são definidas com o uso de regras. Desta forma, se todos os casos base e regras se demonstrarem calculáveis, então qualquer sistema matemático pode ser também calculado.

Isso pode parecer pouco interessante, mas esse tipo de demonstração é a forma usual de se provar se um cálculo é impossível. Isso pode economizar um bom tempo. Por exemplo, esse procedimento era usado para provar que a área de um círculo não é uma simples razão de seu diâmetro, e que nenhum ângulo pode ser triseccionado com régua e compasso – ambos enigmas que fascinaram os antigos.

Recursão em ciência da computação

Um método comum de simplificação é dividir o problema em subproblemas do mesmo tipo. Como técnica de programação, este método é conhecido como dividir e conquistar e é a chave para a construção de muitos algoritmos importantes, bem como uma parte fundamental da programação dinâmica.

A recursão na programação é bem exemplificada quando uma função é definida em termos de si mesma. Um exemplo da aplicação da recursão são os parsers (analisadores gramaticais) para linguagens de programação. Uma grande vantagem da recursão é que um conjunto infinito de sentenças possíveis, designs ou outros dados podem ser definidos, analisados ou produzidos por um programa de computador finito.

Relações de recorrência são equações que definem uma ou mais sequências recursivamente. Alguns tipos específicos de relações de recorrência podem ser “resolvidos” para que se obtenha uma definição não-recursiva.

Um exemplo clássico de recursão é a definição da função fatorial, dada aqui em pseudocódigo:

função fatorial(n)
{
  se (n <= 1)
    retorne 1;
  senão
    retorne n * fatorial(n-1);
}

A função chama a si mesma recursivamente em uma versão menor da entrada (n - 1) e multiplica o resultado da chamada por n, até que alcance o caso base, de modo análogo à definição matemática de fatorial.

Um exemplo de algoritmo recursivo é o procedimento que “processa” (faz alguma coisa com) todos os nós de uma árvore:

procedimento ProcessarArvore(no)
{
  ProcessarNo(no);    // realiza a operação específica com o nó primeiramente fornecido
  paracada no_filho de no faça ProcessarArvore(no_filho);
}

Para processar a árvore completa, o procedimento é chamado com o nó raiz representando o parâmetro inicial da árvore. O procedimento chama a si mesmo recursivamente para todos os nós filhos do nó fornecido (i.e. sub-árvores da árvore inicial), até alcançar o caso base que é o nó que não possui nenhum nó filho (i.e. árvore sem galhos, usualmente chamada “folha”).

A árvore por si só pode ser definida recursivamente (e então destinada a processos recursivos) como segue:

estrutura no
{
  no_filho : listar<no>;
  ...
}

estrutura arvore
{
  raiz : no;
  ...
}

A árvore é representada por seu nó raiz apresentando uma lista de nós filhos. Cada nó filho por sua vez tem sua própria lista de nós filhos (assim como o nó raiz de uma sub-árvore). A "folha" que não possuir uma lista de nós filhos será o caso base de no.

O teorema da recursão

Na teoria dos conjuntos, este é um teorema que garante que uma função definida recursivamente irá existir. Dado um conjunto $X$ , um elemento $a$ de $X$ e uma função $f:X\rightarrow X$ , o teorema indica que há uma única função $F:\mathbb {N} _{0}\rightarrow X$ (onde $N_{0}$ denota o conjunto dos números naturais) tal que: