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.

[ Hits: 70.476 ]

Por: Jarno Trulli em 19/10/2004


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:
  1. um disco de número menor não pode estar debaixo de um disco maior;
  2. 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");

   hanoi(total_discos,'A','B','C');
   printf("\n\n\n");
}

No arquivo hanoi.h:

#include<stdio.h>

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

Página anterior     Próxima página

Páginas do artigo
   1. Para começar, alguns problemas recursivos
   2. A Seqüência de Fibonacci
   3. Torres de Hanoi
   4. Conclusão (ou não!)
Outros artigos deste autor

GNU Emacs (Intro)

Rage Against Binary Blob - sobre documentação aberta para hardware

BOCHS - O emulador de x86

Leitura recomendada

O ? Alternativo em C/C++

Introdução à linguagem C - Parte III

Linguagem C - O primeiro programa

Vírus de computador e criação de um vírus em C/C++ (parte 1 - básico)

Utilizando a função QSort em C

  
Comentários
[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 :)

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

[2] Comentário enviado por Ragen em 19/10/2004 - 15:55h

kekeke

Jarno,

Usou exemplos da lista de exercicios de recursividade de ICC2 da UCG (Pra quem na sabe - Universidade Catolica de Goias)?

[]`s

Ragen

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

[4] Comentário enviado por josefilhofla em 21/10/2004 - 00:38h

Alguem pode me enviar o algoritmo torres de hanoi versão não recursiva.

[5] Comentário enviado por zalves em 23/11/2005 - 14:27h

Galera
alguem sabe como fica o teste de mesa

Como fica a string após aaargh (nome,0,4)

Char nome = mari

Void troca(int v[],int i, int j){
Int temp;
Temp = v[i];
V [i] = v[j];
V [j] = temp;}

Void aaargh ( int v[ ], int esq, int dir ){
Int i ; int ultimo;

If ( esq > dir ){
Return;}

Troca ( v, esq ( esq + dir)/2);
Ultimo = esq ;

For (i= esq+1; i< dir; i++)

if(v [i] < v[esq] ){
ultimo + = 1;
troca ( v,ultimo, i ); }

troca(v,esq,ultimo);
aaargh(v,esq,ultimo-1);
aaargh(v,ultimo+1);
}

[6] Comentário enviado por lequinho em 16/04/2006 - 18:50h

Não gostei desta implementação da recursão, tendo ainda alguns erros e tb, poderia ter melhorado, eu faria assim:

#include <stdio.h>

int soma(int n)
{
if(n==0)
return(0);
else
return(n + soma(n-1));
}

void main()
{
int n;

printf("Entre com um valor : ");
scanf(" %d", &n);

printf("Soma: %d",soma(n));
printf("\n\n");

}

Muito simples nao ?


[7] Comentário enviado por luiz ferreira em 29/08/2006 - 21:37h

caro amigos boa noite..tenho muita dificuldade em aprender c++ e algoritmo caso possa me ajudar..
Grato:Luiz Fabiano

[8] Comentário enviado por arielmoreira em 10/01/2007 - 14:04h

ola

[9] Comentário enviado por arielmoreira em 10/01/2007 - 14:15h

Ola josefilhofla,segue abaixo o algoritmo para as torre de hanoi
entretanto alguem tem uma ideia de como resolver o cavalo de euler?

#include
#include


struct DADOS {//criando a forma
int disco;
int indice;
char origem;
char destino;
struct DADOS *prox;
};
typedef struct DADOS * HANOI ;

HANOI Estado_inicial(HANOI inicio) {
inicio = (HANOI) malloc(sizeof(struct DADOS));
inicio->prox = NULL;
return inicio;
}
HANOI Insere(HANOI inicio,int tipo,int id ,char og,char dt) {
HANOI aux;
aux=(HANOI)malloc(sizeof(struct DADOS));
aux->disco=tipo;
aux->indice=id;
aux->origem=og;
aux->destino=dt;
aux->prox=inicio->prox;
inicio->prox=aux;
return inicio;
}

funct(int w){//funcao para colocar os indice dos disco
return w*2;
}

HANOI Busca_Ordenada(HANOI inicio,int tamanho){//ordena as disco na base do indice
HANOI aux=inicio;
int maior,menor,i=0,k=0,d;
char a,b;

while(i < tamanho){
i++;
while(k < tamanho){
k++;
if(aux->indice > aux->prox->indice){
maior=aux->indice;
a=aux->origem;
b=aux->destino;
d=aux->disco;
aux->disco=aux->prox->disco;
aux->indice=aux->prox->indice;
aux->origem=aux->prox->origem;
aux->destino=aux->prox->destino;
aux->prox->indice=maior;
aux->prox->origem=a;
aux->prox->destino=b;
aux->prox->disco=d;

}
aux=aux->prox;
}
k=0;
aux=inicio;
}
i=0;

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;

for( k=1 ; k <= i ; k++){
if(k > 1){
w=s*2;
}
s=w;
b*=2;
quantos=vet[k];//recebe a quantidades de combinacoes
if(k%2 != 0){//primeira condicao
ind=0;
while(++ind <= quantos){//ENCONTRAR O PRIMEIRO DISCO
x++;
ka=(ind-1)%3;
if((ka == 0)){
DISCO=Insere(DISCO,k,w,'a','b');
}else if((ind%3) == 0){
DISCO=Insere(DISCO,k,w,'c','a');
}else if((ind%3 != 0)){
DISCO=Insere(DISCO,k,w,'b','c');
}
w+=b;
}
}else{
ind=0;
while(++ind <= quantos){
x++;
ka=(ind-1)%3;
if((ka == 0)){
DISCO=Insere(DISCO,k,w,'a','c');
}else if((ind%3) == 0){
DISCO=Insere(DISCO,k,w,'b','a');
}else if((ind%3 != 0)){
DISCO=Insere(DISCO,k,w,'c','b');
}
w+=b;
}

}//fim laco if
}//fim laco for

Busca_Ordenada(DISCO,x);





system("PAUSE");
return 0;
}
//arielmoreira

[10] Comentário enviado por venyton em 22/08/2007 - 10:58h

alguem aí sabe como resolver o problema com 4 hastes e N discos utilizando recursão?

[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++.

#include<stdio.h>

int fibonacci_recursivo(int n){

int fib;/*para guardar os números de Fibonacci*/

if(n==1){
fib=1;
}
else{
if (n==2){
fib=1;
}
else{
fib=fibonacci_recursivo(n-1)+fibonacci_recursivo(n-2);
}
}
return fib;
}

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


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts