Mais sobre recursividade em C/C++

Jarnotrulli

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.964 ]

Por: Jarno Trulli em 19/10/2004

1 0

Denuncie Favoritos Indicar Impressora

A Seqüência de Fibonacci

Uma das seqüencias recursivas mais famosas é, certamente, a Sucessão de Fibonacci, definida assim:

F(1)=F(2)=1,
F(n+2)=F(n+1)+F(n) para n>0.

Isto já nos da um programinha recursivo:

No arquivo recursivo_fibonacci.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(n-1)+fibonacci(n-2);
      }
   }
   return fib;
}

int main(void){

   printf("Digite o número!");
   scanf("%d",n);
   printf("fibonacci(%d)=%d",n,fibonacci_recursivo(n))

   return 0;
}

Agora vamos construir uma versão não-recursiva. Primeiro, como fazer isso? Vamos pensar. Quando estamos fazendo as contas na mão, seguimos este procedimento para calcular F(10):

F(1)=1
F(2)=1
F(3)=F(2)+F(1)=1+1=2
F(4)=F(3)+F(2)=2+1=3
F(5)=F(4)+F(3)=3+2=5
F(6)=F(5)+F(4)=5+3=8
F(7)=F(6)+F(5)=8+5=13
F(8)=F(7)+F(6)=13+8=21
F(9)=F(8)+F(7)=21+13=34
F(10)=F(9)+F(8)=34+21=55

Que idéia estamos usando? Simples: a cada momento, pegamos os dois valores anteriores e somamos (sem nem se preocupar com as contas anteriores!). Em um computador, podemos pensar assim: reservar três variáveis (digamos, baixo_f, alto_f e fib) e a cada momento somar as duas primeiras e jogar na terceira, sem esquecer de gravar as duas posições anteriores! Parece meio complicado, não? Então, vamos implementar a coisa para ver como funciona!

No arquivo iterativo_fibonacci.c:

#include<stdio.h>

int fibonacci_iterativo(int n){

   int baixo_f=0,alto_f=0,fib=1;

   for(i=1;i<=n;i++){
   baixo_f=alto_f;
   alto_f=fib;
   fib=baixo_f+alto_f;
   }

return fib;
}

int main(void){

   printf("Digite o número!");
   scanf("%d",n);
   printf("fibonacci(%d)=%d",n,fibonacci_iterativo(n))

  return 0;
}

Veja que a versão iterativa perde um pouco em clareza comparado com a versão recursiva, mas a rapidez compensa algumas dessas perdas.

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

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

GNU Emacs (Intro)

BOCHS - O emulador de x86

Leitura recomendada

Estudo de ponteiros para GNU/Linux

Linguagem C - O primeiro programa

Introdução à ponteiros em C

Introdução à linguagem C - Parte II

Criando uma aplicação gráfica com o Qt Designer

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

0 0

[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

0 0

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

0 0

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

0 0

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

0 0

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

0 0

[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

0 0

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

ola

0 0

[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

0 0

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

0 0

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

0 0