Preciso estudar sempre: Entrando em várias realidades com recursividade

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Você já viu o filme "Inception" ou, em português "A Origem" ?

Figura 1 - Filme Inception

Tá .... você que acompanha o blog deve estar se perguntando porque eu estou falando sobre esse filme, se o nosso foco aqui é outro.

Calma !!! Não viramos um blog de cinema, mas recomendo fortemente que você veja esse filme.

Se você viu, sabe que ele é bom, mas se não, fique tranquilo pois não darei spoilers. O filme trata sobre pessoas que conseguem sonhar e dentro deles, conseguem sonhar novamente. Resumidamente, eles sonham que estão sonhando e podem fazer isso de infinitamente.

Mas então ... o que isso tem haver conosco ? Onde isso se encaixa ?

Existe uma técnica de programação que utiliza esse mesmo conceito.
Sim, você não leu errado, e não, não iremos criar programas que são capazes de sonhar, pois caso fizéssemos a Skynet seria uma realidade.

Essa técnica se chama recursividade.

Figura 2 - Cena do filme Exterminador do futuro

A recursividade é algo mágico na computação. Ela nos permite abordar problemas de uma forma completamente diferente, mas deve ser usada com sabedoria, pois como já discutimos aqui, não existem balas de prata. Devemos saber quando e onde aplicar nossos novos conhecimentos.

Na computação existe uma técnica para abordar problemas, conhecida como "dividir para conquistar". Ela define que para um problema P muito grande, onde não é possível resolvê-lo de uma vez só, devemos dividi-lo por 2. Se essas metades (P/2) ainda forem grandes, devemos dividi-los novamente por 2, gerando P/4. Esse processo deve ser repetido até o momento em que o problema se torne pequeno o bastante para poder ser resolvido. A partir disso, a mesma solução é aplicada para todas as partículas geradas.

Mas o que determina quando devemos parar de dividir o problema ?

O caso base de uma solução recursiva é a parte responsável por essa tarefa. Toda abordagem recursiva deve possuir um caso base, pois caso contrário um loop infinito seria gerado. Contudo, como é possível construir um programa com tais características ?

Para que um algoritmo possa ter a inteligência recursiva, ele precisa implementar o seu caso base e para a divisão do problema, ele deve realizar chamadas a si mesmo. Porém, isso não soa errado? Como um método ou função vai se chamar ?

Ao contrário do que a maioria pensa, uma chamada à um método ou função é nada mais que uma transferência de controle de um método de origem para um de destino. No caso de uma chamada recursiva, é uma transferência para o seu próprio início.

Vamos analisar o seguinte exemplo !

Você quer criar um programa que calcule fatoriais para números inteiros positivos. É sabido que o fatorial de um número é a multiplicação dele por seus antecessores e que o fatorial de 0 é 1. Logo, 5! (lê-se cinco fatorial) é igual a 5 * 4 * 3 * 2 * 1, por exemplo.

No nosso programa não podemos engessar nossas soluções. Devemos ser capazes de receber um número e retornar seu fatorial, mas como fazer isso se não sabemos qual número será ? Contudo, se pararmos para pensar, chegamos a conclusão que um fatorial de um número n é igual a n multiplicado pelo fatorial de (n-1). Logo, é possível afirmar que 5! = 5 * 4!.

Mas, qual é o valor de 4! ? Utilizando o mesmo conceito, sabemos que 4! = 4 * 3!. Então, quando paramos ? Qual é o número que não precisa ser multiplicado pelo seu antecessor para que saibamos seu fatorial ? A resposta é clara, o número procurado é o 0. Acabamos de estabelecer o nosso caso base. Cada problema que pode ser resolvido de forma recursiva tem o seu. Cabe a você analisar e encontrá-lo.

Já podemos montar o nosso algoritmo recursivo, pois já sabemos quando devemos dividir o problema e quando devemos parar.

1:  public int fatRecursive(int valor){  
2:       if(valor == 0){  
3:            return 1;  
4:       }  
5:       return valor * fatRecursive(valor-1);  
6:  }

Note que na linha cinco multiplicamos a variável valor pela chamada recursiva de fatRecursive, a qual recebe como parâmetro valor-1. Para que possamos entender melhor como nosso método funciona, vamos chamar essa primeira execução de e1. A partir da chamada, uma nova execução é feita, começando do início, gerando e2. Lembre-se que e1 ainda não terminou. Ela ainda está presa na linha cinco, pois está esperando e2 terminar.

A partir de e2 é gerado e3, e dessa forma são geradas outras execuções até o nosso caso base ser atingido. No momento em que é alcançado, as execuções que outrora estavam indo para frente agora voltam pelo caminho que fizeram e a última execução desbloqueia sua anterior, ou seja, se a última execução era e5, ela desbloqueia e4, que desbloqueia e3 e esse processo é repetido até e1, finalizando assim a execução completa do programa.

Agora que já temos total entendimento de como uma lógica recursiva funciona, nós devemos refletir sobre a seguinte questão: é possível resolver um problema recursivo com laços de repetição ? Alguns problemas sim mas, outros não.

Para o problema acima, poderíamos ter utilizado o seguinte código.

1:  public int fatNonRecursive(int valor){  
2:       int valorFat=1;  
3:       for (int i=1; i<=valor; i++) {  
4:            valorFat = valorFat * i;  
5:       }  
6:       return valorFat;  
7:  }

E aí !? Qual usar ?

Como eu disse anteriormente, não existem balas de prata. Não existe maneira alguma de afirmar que a recursão é melhor que os laços de repetição, ou vice e versa. Cada abordagem tem suas características. Como nosso exemplo é algo bem simples, para fins de estudo, não justifica o uso da recursividade. A recursão é geralmente usada porque simplifica um problema conceitualmente, não porque é mais eficiente. Utilizá-la resulta em overhead, visto que várias chamadas ao mesmo método são feitas, causando assim uma lentidão se comparada à abordagem com laços (Lafore R.).

Deixo aqui disponível para download outros exemplos de algoritmos recursivos, são eles: