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.
Vamos falar de um problema clássico: as Torres de Hanoi!
O problema consiste numa pilha de n discos, numeradas de 1 a n, e 3 hastes (ou pilhas). O jogo funciona assim:
um disco de número menor não pode estar debaixo de um disco maior;
podemos retirar apenas o disco superior de uma determinada pilha.
Tente fazer um desenho para entender melhor as idéias por trás desse problema, enquanto eu sigo o meu desenho e tento explicar:
Em primeiro lugar, vamos definir as entradas e saídas. Não é difícil ver que o número de entradas é simplesmente o número n de discos. Já as saídas poderão ser as mais variadas (por exemplo, uma tela de animação). Vamos adotar a saída em modo texto, com instruções no seguinte formato:
Mova o disco x da haste L ate a haste M.
Para facilitar as idéias, vamos chamar as hastes de:
1) haste A ou haste de origem
2) haste B ou haste auxiliar
3) haste C ou haste de chegada
Podemos resolver esse problema recursivamente, assim: se há apenas um disco, movemos ele da haste A ate a haste C.
Agora suponha que você tenha n discos, com n pelo menos dois, e que você aprendeu a fazer o problema para qualquer números de discos menor que n. Então, esse algoritmo diz como resolver para n+1:
1) Mova os n-1 primeiros discos de A ate B;
2) Mova o disco n de A ate C;
3) Mova os discos da haste B ate a haste C.
Agora sim, já podemos partir para o algoritmo!
No arquivo hanoi.c:
#include"hanoi.h"
int main (void){
int total_discos;
extern void hanoi (int discos , char origem, char destino, char ajuda);
/* Uma alusão a função hanoi */
printf("\t Introduza o número de discos: ");
scanf("%d",&total_discos);
printf ("\n\n\n");
void hanoi (int discos, char origem, char destino, char ajuda){
if (discos==1){
printf("\t Mova o disco %d de %c para %c \n",discos,origem, destino);
}
else{
hanoi(discos-1,origem,ajuda,destino);
printf("\t Mova o disco %d de %c para %c \n",discos,origem,destino);
hanoi(discos-1,ajuda,destino,origem);
}
}
Divirtam-se!! Tentem também construir uma versão não-recursiva!
Como exercício, vai uma proposta: dissemos, há algumas linhas acima, que as saídas poderiam ter os mais diversos formatos. Generalize este último algoritmo, para que possamos aplicá-lo em qualquer situação de saída (por exemplo, imagine que o usuário desse pequeno programa queira várias opções de saídas: textual, gráfica, as duas ao mesmo tempo. A sua nova função hanoi será independente dessas escolhas).
[1] Comentário enviado por jllucca em 19/10/2004 - 15:54h
Assim, durante todo o artigo vi uma coisa que não gostei que é a criação de uma variavel "auxiliar" para a recursão. No primeiro exemplo isso ocorre e queria sugerir uma mudança para algo mais limpo :)
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 :)
[3] Comentário enviado por Jarnotrulli em 19/10/2004 - 17:29h
Nao ate onde eu sei!
Eu raramente faço exercicios( :-) ).
Esse foi um dos exemplos que a minha professora de ICC1 tinha dado em aula (so tive o trabalho de traduzir os codigos em linguagem C).
Alias, eu sempre esqueço quem e o primeiro Fibonacci (:-/).
Talvez ate por isso mesmo alguns codigos nao tenham ficado muuito bons (traduçao literal funciona muito bem mas...).
Esses merecem uma correçao mais apurada.
Obrigado pelas criticas!
E alias, aonde eu acho essa lista de exercicios?
while(i < tamanho){
i++;
printf(" Move o Disco %d de %c para %c \n",aux->disco,aux->origem,aux->destino);
aux=aux->prox;
}
return inicio;
}
int main(int argc, char *argv[]){
HANOI DISCO;
DISCO=Estado_inicial(DISCO);
long int i,y=1,a,k,vet[100],x=0,b=1,ind=0,ka,e=0,w=1,quantos,gamb=1,s=1;
printf("QUANTOS DISCOS?\n");
scanf(" %d",&i);
a=i;
k=i;
while( i >= 1 ){ //encontrar o numero de discos com as combinacoes
vet[k]=y;
k--;
y+=y;
--i;
}
i=a;
[11] Comentário enviado por marcos@marcos em 21/08/2012 - 10:08h
Bom dia!
Caro colega, pelo que entendi então seu código vai imprimir apenas o valor da posição "n", onde n é o número informado pelo usuário. Acho que uma pequena alteração de forma a permitir que seja impresso, por exemplo, quando o usuário digitar 5, o algoritmo deverá imprimir os 5 primeiros termos da série.
Abaixo o código já alterado para que aconteça o que foi descrito acima. Quero antes de tudo, também, ressaltar que tentando disponibilizar um código o mais didático possível, afinal sou um mero iniciante em c/c++.
int main(void){
int n,y=0;
printf("Digite o número!");
scanf("%d",&n);
printf("%d",y); //garantindo que o primeiro elemento seja sempre zero
/*o loop abaixo tem a finalidade */
for(int i=0; i<n-1;i++){
printf(" %d",fibonacci_recursivo(i+1));
}
return 0;
}