Ava Anhanguera

Recursividade

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

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