O Que é Recursividade ?
Autor: Pedro Luis Kantek Garcia Navarro
Alguma coisa é recursiva quando é definida em termos dela própria. O grande apelo que o conceito da recursão traz é a possibilidade de dar uma definição finita para um conjunto que pode ser infinito. Eis um exemplo da aritmética, bem simples, aquele que dá a definição dos números naturais, em termos dos axiomas de Peano:
O primeiro natural é o zero.
O sucessor de um número natural é um número natural.
A recursividade é uma daquelas idéias em informática (como algumas da vida comum) que em geral dividem a população em dois grupos antagônicos: os que são francamente favoráveis, em geral impressionados com a elegância e aparência de simplicidade dos algorítmos recursivos, e os que a consideram uma frivolidade a ser evitada a todo custo. No caso da recursividade, talvez haja que se acrescentar um terceiro grupo: o daqueles que não a conhecem, ou nunca chegaram a entendê-la, e que, talvez por isso, com maior facilidade se alinhem no segundo grupo. Uma possível explicação para esse desconforto vem da sensação de que a recursividade leva o procedimento ao infinito e este conceito tem assustado o homem desde a antigüidade.
Veja-se a seguir alguma coisa do primeiro homem a estudar profundamente o infinito. Seu nome: Georg Cantor.
Nascido em São Petersburgo, passou a maior parte da vida na Alemanha. Seu pai converteu-se ao protestantismo, e sua mãe nasceu católica, mas ambos eram de ascendência judia. O interesse inicial de Cantor foi pelos argumentos medievais sobre continuidade e infinito. O pai queria que ele fosse engenheiro, mas ele preferiu algo bem mais sutil. Estudou filosofia, física e matemática e doutorou-se em Berlim em 1867, com uma tese sobre a teoria dos números. Desde a Grécia antiga se falava em infinito, mas parece que ninguém sabia direito do que se falava.
A primeira definição formal de infinito é devida a Dedekind (um sistema S é infinito quando é semelhante a uma parte própria dele mesmo). Em 1874, Cantor se casou e na sua lua-de-mel foi à Interlaken onde estava Dedekind. Eles se encontraram e logo depois ele publicou um artigo revolucionário. Concordou com Dedekind na definição de infinito, mas discordou dizendo que há infinitos e infinitos. No caso dos finitos, dizemos que dois conjuntos têm a mesma cardinalidade se seus elementos podem ser colocados em correspondência bi-unívoca. Cantor levou esse mesmo conceito para os conjuntos infinitos. Por exemplo, pode-se provar que há tantos números pares quanto números inteiros. Ambos são infinitos, mas têm a mesma cardinalidade, já que a relação n <-p, sempre pode ser estabelecida n inteiro e p um par, sendo que p="2n)." Como ambos são conjuntos infinitos, essa relação sempre pode ser estabelecida e com isso, pode-se concluir que ambos conjuntos têm a mesma cardinalidade.
Outro exemplo: sempre se achou que os racionais (na forma p/q) seriam em maior número que os inteiros, já que entre dois racionais sempre é possível inserir um novo. Graças a um arranjo triangular bem sacado, Cantor provou que os racionais também podem ser postos em equivalência com os inteiros e, portanto, são enumeráveis, logo, a cardinalidade dos racionais é a mesma dos inteiros. Mesmo os algébricos que são mais gerais que os racionais, continuam tendo a mesma cardinalidade.
Pode-se pensar que todos os infinitos têm a mesma cardinalidade, mas novamente Cantor provou que não é verdade. Os reais têm cardinalidade maior. A prova é simples e elegante, por reductio ad absurdum. Suponhamos que eles são contáveis. Então será possível criar uma tabela do tipo
0,a11 a12 a13 ...
0,a21 a22 a23 ...
0,a31 a32 a33 ...
...
Cantor propôs um real 0,b1 b2 b3... construído segundo a regra: sempre que akk for igual a 1, bk será 5, e se akk for diferente de 1, bk será 1. Esse número assim construído será um real compreendido entre 0 e 1, e no entanto não fará parte da lista que supostamente tinha todos os reais. Logo...
A conclusão é que são os números transcendentes que dão aos reais essa característica de inumerabilidade. Ele chamou a cardinalidade dos inteiros de aleph zero, e a dos reais de C (de continuum). Ainda não se sabe se existem cardinalidades entre aleph zero e C, embora saiba-se existirem infinitos números de cardinalidade depois de C.
Ele trabalhou numa aritmética de números cardinais, onde por exemplo w+1 é diferente de 1+w, e w+w=w, onde w é um número cardinal. Alguns resultados do trabalho de Cantor eram tão paradoxais que ele mesmo escreveu "vejo isso, mas não acredito". Em 1884 sofreu o primeiro dos esgotamentos nervosos que o perseguiriam pelos 33 anos restantes de sua vida. Morreu em 1918 num hospital para doentes mentais. Como se pode ver, genialidade e loucura andam sempre meio próximas. Entretanto, Hilbert, outro grande matemático do século XX escreveu: "Ele entrou onde almas tímidas tinham hesitado. Ninguém nos expulsará do paraíso que Cantor criou para nós".
Voltando ... recursividade, um programador digno do nome terá que conhecê-la, entendê-la e estar pronto a usá-la quando for a melhor (ou as vezes única) alternativa. Em geral, salvo raras exceções, uma solução recursiva admite um algoritmo equivalente não recursivo. E também em geral, tal solução não recursiva exige maior código, embora este seja mais facilmente entendível, com exceção daquelas (poucas) pessoas que conseguem ver a recursividade como algo claro e límpido.
Mas, afinal, o que é a recursividade ? É a descrição de algo em termos dele mesmo. Só que para que a definição não seja circular (e portanto infinita), a descrição recursiva deve ser dada em termos "menores" que a definição original. É esse "menor" que faz com que em algum momento, o ciclo se encerre e a definição esteja completa. Qual o sentido e o significado desse menor? Varia de caso a caso, e é muito difícil dar uma definição geral.
Vamos examinar um exemplo coloquial de procedimento recursivo. Imaginemos ter que achar o significado da palavra "palombeta" no dicionário Aurélio. Obviamente, a ninguém ocorre a tentação de ler seqüencialmente o dicionário até chegar ... palavra procurada. (ainda que a leitura descompromissada do Aurélio sempre reserve boas e divertidas surpresas).
Definamos o processo de achar uma palavra num dicionário em termos algorítmicos mais ou menos livres procura-palavra (Dicionário, palavra-procurada)
abrir o dicionário na metade palavra-pivot1 ( a primeira palavra da página impar aberta)
palavra-pivot2 ( a última palavra da página par aberta) se palavra-procurada palavra-pivot1
* procura-palavra (primeira-metade do dicionário, palavra-procurada)
fim {se}
se palavra-procurada palavra-pivot2
* procura-palavra (segunda metade do dicionário, palavra-procurada)
fim {se}
se palavra-procurada palavra-pivot1 E palavra-procurada palavra-pivot2
* ler seqüencialmente as duas páginas
se palavra-procurada for encontrada
* imprimir a sua definição
fim do algoritmo
fim {se}
se palavra-pivot2 for encontrada
* imprimir ("palavra procurada não existe")
fim do algoritmo
fim {se}
fim da leitura seqüencial
fim {se}
fim
O algoritmo é recursivo no sentido de que ele chama a ele mesmo. Veja-se que o nome do algorítmo, aparece também 2 vezes dentro dele mesmo. Nesse caso, o processo é finito, já que a cada chamada o universo de pesquisa é menor. Na primeira vez, ele é todo o dicionário, na segunda vez, apenas a metade, na terceira vez, uma quarta parte e assim por diante. Finalmente, há uma condição que estabelece o fim da pesquisa (quando as páginas que contém a palavra procurada forem abertas).
No exemplo do dicionário vimos as 3 características que um problema recursivo tem que ter:
Um processo que chame a si mesmo.
A garantia de que a cada chamada, o universo de trabalho do processo será "menor". Uma condição, que obrigatoriamente ocorrerá, que indique quando terminar.
Alguma coisa é recursiva quando é definida em termos dela própria. O grande apelo que o conceito da recursão traz é a possibilidade de dar uma definição finita para um conjunto que pode ser infinito. Eis um exemplo da aritmética, bem simples, aquele que dá a definição dos números naturais, em termos dos axiomas de Peano:
O primeiro natural é o zero.
O sucessor de um número natural é um número natural.
A recursividade é uma daquelas idéias em informática (como algumas da vida comum) que em geral dividem a população em dois grupos antagônicos: os que são francamente favoráveis, em geral impressionados com a elegância e aparência de simplicidade dos algorítmos recursivos, e os que a consideram uma frivolidade a ser evitada a todo custo. No caso da recursividade, talvez haja que se acrescentar um terceiro grupo: o daqueles que não a conhecem, ou nunca chegaram a entendê-la, e que, talvez por isso, com maior facilidade se alinhem no segundo grupo. Uma possível explicação para esse desconforto vem da sensação de que a recursividade leva o procedimento ao infinito e este conceito tem assustado o homem desde a antigüidade.
Veja-se a seguir alguma coisa do primeiro homem a estudar profundamente o infinito. Seu nome: Georg Cantor.
Nascido em São Petersburgo, passou a maior parte da vida na Alemanha. Seu pai converteu-se ao protestantismo, e sua mãe nasceu católica, mas ambos eram de ascendência judia. O interesse inicial de Cantor foi pelos argumentos medievais sobre continuidade e infinito. O pai queria que ele fosse engenheiro, mas ele preferiu algo bem mais sutil. Estudou filosofia, física e matemática e doutorou-se em Berlim em 1867, com uma tese sobre a teoria dos números. Desde a Grécia antiga se falava em infinito, mas parece que ninguém sabia direito do que se falava.
A primeira definição formal de infinito é devida a Dedekind (um sistema S é infinito quando é semelhante a uma parte própria dele mesmo). Em 1874, Cantor se casou e na sua lua-de-mel foi à Interlaken onde estava Dedekind. Eles se encontraram e logo depois ele publicou um artigo revolucionário. Concordou com Dedekind na definição de infinito, mas discordou dizendo que há infinitos e infinitos. No caso dos finitos, dizemos que dois conjuntos têm a mesma cardinalidade se seus elementos podem ser colocados em correspondência bi-unívoca. Cantor levou esse mesmo conceito para os conjuntos infinitos. Por exemplo, pode-se provar que há tantos números pares quanto números inteiros. Ambos são infinitos, mas têm a mesma cardinalidade, já que a relação n <-p, sempre pode ser estabelecida n inteiro e p um par, sendo que p="2n)." Como ambos são conjuntos infinitos, essa relação sempre pode ser estabelecida e com isso, pode-se concluir que ambos conjuntos têm a mesma cardinalidade.
Outro exemplo: sempre se achou que os racionais (na forma p/q) seriam em maior número que os inteiros, já que entre dois racionais sempre é possível inserir um novo. Graças a um arranjo triangular bem sacado, Cantor provou que os racionais também podem ser postos em equivalência com os inteiros e, portanto, são enumeráveis, logo, a cardinalidade dos racionais é a mesma dos inteiros. Mesmo os algébricos que são mais gerais que os racionais, continuam tendo a mesma cardinalidade.
Pode-se pensar que todos os infinitos têm a mesma cardinalidade, mas novamente Cantor provou que não é verdade. Os reais têm cardinalidade maior. A prova é simples e elegante, por reductio ad absurdum. Suponhamos que eles são contáveis. Então será possível criar uma tabela do tipo
0,a11 a12 a13 ...
0,a21 a22 a23 ...
0,a31 a32 a33 ...
...
Cantor propôs um real 0,b1 b2 b3... construído segundo a regra: sempre que akk for igual a 1, bk será 5, e se akk for diferente de 1, bk será 1. Esse número assim construído será um real compreendido entre 0 e 1, e no entanto não fará parte da lista que supostamente tinha todos os reais. Logo...
A conclusão é que são os números transcendentes que dão aos reais essa característica de inumerabilidade. Ele chamou a cardinalidade dos inteiros de aleph zero, e a dos reais de C (de continuum). Ainda não se sabe se existem cardinalidades entre aleph zero e C, embora saiba-se existirem infinitos números de cardinalidade depois de C.
Ele trabalhou numa aritmética de números cardinais, onde por exemplo w+1 é diferente de 1+w, e w+w=w, onde w é um número cardinal. Alguns resultados do trabalho de Cantor eram tão paradoxais que ele mesmo escreveu "vejo isso, mas não acredito". Em 1884 sofreu o primeiro dos esgotamentos nervosos que o perseguiriam pelos 33 anos restantes de sua vida. Morreu em 1918 num hospital para doentes mentais. Como se pode ver, genialidade e loucura andam sempre meio próximas. Entretanto, Hilbert, outro grande matemático do século XX escreveu: "Ele entrou onde almas tímidas tinham hesitado. Ninguém nos expulsará do paraíso que Cantor criou para nós".
Voltando ... recursividade, um programador digno do nome terá que conhecê-la, entendê-la e estar pronto a usá-la quando for a melhor (ou as vezes única) alternativa. Em geral, salvo raras exceções, uma solução recursiva admite um algoritmo equivalente não recursivo. E também em geral, tal solução não recursiva exige maior código, embora este seja mais facilmente entendível, com exceção daquelas (poucas) pessoas que conseguem ver a recursividade como algo claro e límpido.
Mas, afinal, o que é a recursividade ? É a descrição de algo em termos dele mesmo. Só que para que a definição não seja circular (e portanto infinita), a descrição recursiva deve ser dada em termos "menores" que a definição original. É esse "menor" que faz com que em algum momento, o ciclo se encerre e a definição esteja completa. Qual o sentido e o significado desse menor? Varia de caso a caso, e é muito difícil dar uma definição geral.
Vamos examinar um exemplo coloquial de procedimento recursivo. Imaginemos ter que achar o significado da palavra "palombeta" no dicionário Aurélio. Obviamente, a ninguém ocorre a tentação de ler seqüencialmente o dicionário até chegar ... palavra procurada. (ainda que a leitura descompromissada do Aurélio sempre reserve boas e divertidas surpresas).
Definamos o processo de achar uma palavra num dicionário em termos algorítmicos mais ou menos livres procura-palavra (Dicionário, palavra-procurada)
abrir o dicionário na metade palavra-pivot1 ( a primeira palavra da página impar aberta)
palavra-pivot2 ( a última palavra da página par aberta) se palavra-procurada palavra-pivot1
* procura-palavra (primeira-metade do dicionário, palavra-procurada)
fim {se}
se palavra-procurada palavra-pivot2
* procura-palavra (segunda metade do dicionário, palavra-procurada)
fim {se}
se palavra-procurada palavra-pivot1 E palavra-procurada palavra-pivot2
* ler seqüencialmente as duas páginas
se palavra-procurada for encontrada
* imprimir a sua definição
fim do algoritmo
fim {se}
se palavra-pivot2 for encontrada
* imprimir ("palavra procurada não existe")
fim do algoritmo
fim {se}
fim da leitura seqüencial
fim {se}
fim
O algoritmo é recursivo no sentido de que ele chama a ele mesmo. Veja-se que o nome do algorítmo, aparece também 2 vezes dentro dele mesmo. Nesse caso, o processo é finito, já que a cada chamada o universo de pesquisa é menor. Na primeira vez, ele é todo o dicionário, na segunda vez, apenas a metade, na terceira vez, uma quarta parte e assim por diante. Finalmente, há uma condição que estabelece o fim da pesquisa (quando as páginas que contém a palavra procurada forem abertas).
No exemplo do dicionário vimos as 3 características que um problema recursivo tem que ter:
Um processo que chame a si mesmo.
A garantia de que a cada chamada, o universo de trabalho do processo será "menor". Uma condição, que obrigatoriamente ocorrerá, que indique quando terminar.