Recursão na linguagem

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 (freqüentemente 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 lingüística, e o uso da recursão em geral, remete ao lingüista 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 lingüista 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:

1. Nós já terminamos? Se sim, retorne os resultados. Sem uma condição de parada como esta, uma recursão iria se repetir eternamente.

2. 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 freqüentemente 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. Conseqüentemente, 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.

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 seqüê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