Mais sobre recursividade em C/C++
Seguindo a linha do artigo do Carlos Alberto, Vamos falar um pouco mais sobre recursividade, uma técnica muito usada para diversos programas. Mostraremos seus prós e contras, bem como alguns (não muitos!) exemplos práticos, como a Seqüência de Fibonacci e as Torres de Hanoi.
Para começar, alguns problemas recursivos
Como já foi dito num artigo anterior, uma função é dita recursiva
quando faz uma chamada a si mesma. Leia mais no artigo do
Carlos Alberto em:
Vamos tomar um exemplo.
Como você calcularia a soma dos naturais de 0 a X, num programa em C?
Um modo seria esse: se X for 0, a soma da zero, e eu já tenho a resposta! Caso contrário, eu somo X com a soma dos naturais calculada de 1 ate X-1. E exatamente assim que implementamos um algoritmo recursivo. Veja esse código:
No arquivo soma.h:
Vamos tomar um exemplo.
Como você calcularia a soma dos naturais de 0 a X, num programa em C?
Um modo seria esse: se X for 0, a soma da zero, e eu já tenho a resposta! Caso contrário, eu somo X com a soma dos naturais calculada de 1 ate X-1. E exatamente assim que implementamos um algoritmo recursivo. Veja esse código:
No arquivo soma.h:
#include <stdio.h>
int soma_recursiva_da_PA(int n){
int soma; /* esta variável guarda o valor da soma a cada chamada.*/
if (n==0){
soma=0;
}
else {
soma=soma+soma_da_PA(n-1);
}
return soma;
}
int soma_nao_recursiva_da _PA(int n){
int soma=0, i;
for(i=0;i<=n;i++){
soma+=i;
}
return n;
}
int soma_recursiva_da_PA(int n){
int soma; /* esta variável guarda o valor da soma a cada chamada.*/
if (n==0){
soma=0;
}
else {
soma=soma+soma_da_PA(n-1);
}
return soma;
}
int soma_nao_recursiva_da _PA(int n){
int soma=0, i;
for(i=0;i<=n;i++){
soma+=i;
}
return n;
}
No arquivo soma.c:
#include "soma.h"
int main (void){
int n,s1,s2;
printf("Digite o número:");
scanf("%d",&n);
s1=soma_recursiva_da_PA(n);
s2=soma_nao_recursiva_da_PA(n);
printf("\nA soma dos números de 1 a %d e: %d ",n,s1);
printf("\nA soma dos números de 1 a %d e: %d ",n,s1);
}
int main (void){
int n,s1,s2;
printf("Digite o número:");
scanf("%d",&n);
s1=soma_recursiva_da_PA(n);
s2=soma_nao_recursiva_da_PA(n);
printf("\nA soma dos números de 1 a %d e: %d ",n,s1);
printf("\nA soma dos números de 1 a %d e: %d ",n,s1);
}
Divertido, não? Mas há um pequeno preço a pagar pela beleza: espaço em memória. Explicaremos o por quê.
Primeiramente faremos o teste de mesa: imagine-se trabalhando como o computador e analise cada passo do algoritmo.
Na versão não-recursiva, ele fará o cálculo de T(10) (o valor da soma de zero a dez) assim:
soma começa de 0; para i de 0 ate n, some i ao valor da soma e jogue em soma(sobrescrever).
Assim, ocorre algo assim nas posições de memória:
soma 0 1 3 6 10 15 21 28 36 45 55 i 0 1 2 3 4 5 6 7 8 9 10Rápido, fácil e simples.
Agora a versão recursiva. Nela, os valores desconhecidos são colocados numa pilha na memória. Veja:
T(10)=T(9)+10
T(9)=T(8)+9
T(8)=T(7)+8
T(7)=T(6)+7
T(6)=T(5)+6
T(5)=T(4)+5
T(4)=T(3)+4
T(3)=T(2)+3
T(2)=T(1)+2
T(1)=T(0)+1=1
Até agora cada valor foi colocado numa pilha, com a ordenação inversa do modo que eu ilustrei.
Assim, agora a máquina irá retornar os valores, um a um:
T(2)=3
T(3)=6
T(4)=10
T(5)=15
T(6)=21
T(7)=28
T(8)=36
T(9)=45
T(10)=55
Sentiu o drama?
Então, segue a dica: não abuse da recursividade! Use-a apenas em situações especiais, tais como:
- Não houver problemas com espaço de memória ou dos registradores;
- Não houver problemas com tempo de execução do programa.
- A solução recursiva ser mais limpa e legível que a não-recursiva.
- For necessário escrever um artigo sobre recursividade :)
Vamos citar outro exemplo:
Como inverter uma cadeia de caracteres digitada pelo usuário?
De um modo recursivo, poderíamos fazer assim:
- Repartir a cadeia em dois pedaços, A e B, de tamanhos quaisquer;
- Recursivamente, inverter A e B, obtendo AT e BT;
- Concatenar BT com AT nessa ordem.
Vamos lá! No arquivo inverter.c:
void inverter (void); /* alusão a função revertora */
int main(void){
printf("Escreva o texto a ser revertido: ");
inverter();
printf("\n\n");
return 0;
}
void inverter(void){
int c;
if ((c=getchar())='\n'){
inverter();
}
putchar(c);
}
int main(void){
printf("Escreva o texto a ser revertido: ");
inverter();
printf("\n\n");
return 0;
}
void inverter(void){
int c;
if ((c=getchar())='\n'){
inverter();
}
putchar(c);
}
Agora vamos para dois programas mais "sérios".
int soma_recursiva_da_PA(int n){
if (n==0){
return n;
}
else {
return n+soma_recursiva_da_PA(n-1); //aqui tava +soma_da_PA(n-1)
}
}
Esse codigo acima, sim mostra como fica elegante e limpo um codigo recursivo. Outro problema, foi no inverter também da primeira pagina.
Dentro da inverter tem apenas a parte que lê do teclado e deveria "jogar" em outra função recursiva. Mas, esta não existe.
Na parte do fibonacci, se não me engano o F0 = F1 e não o F1 = F2. Mas, isso é o de menos. Se funcionar de um jeito so botar -1 que funciona no outro hehehehe
Espero ter ajudado lhe apontando alguns locais onde cometeu deslizes. Para termos cada vez mais artigos melhores e bem conceituados :)
[]'s