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.540 ]
Por: Jarno Trulli em 19/10/2004
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:
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;
}
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;
}
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áginas do artigo
1. Para começar, alguns problemas recursivos2. 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
Leitura recomendada
Inteiros e Strings na linguagem C
Estudo de ponteiros para GNU/Linux
Introdução à linguagem C - Parte II
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
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
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?
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.
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);
}
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 ?
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
caro amigos boa noite..tenho muita dificuldade em aprender c++ e algoritmo caso possa me ajudar..
Grato:Luiz Fabiano
[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
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?
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;
}
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;
}
Patrocínio
Site hospedado pelo provedor RedeHost.
Destaques
Agora temos uma assistente virtual no fórum!!! (247)
Artigos
Manutenção de sistemas Linux Debian e derivados com apt-get, apt, aptitude e dpkg
Melhorando o tempo de boot do Fedora e outras distribuições
Como instalar as extensões Dash To Dock e Hide Top Bar no Gnome 45/46
Dicas
Como Atualizar Fedora 39 para 40
Instalar Google Chrome no Debian e derivados
Consertando o erro do Sushi e Wayland no Opensuse Leap 15
Instalar a última versão do PostgreSQL no Lunix mantendo atualizado
Flathub na sua distribuição Linux e comandos básicos de gerenciamento
Tópicos
Top 10 do mês
-
Xerxes
1° lugar - 74.556 pts -
Fábio Berbert de Paula
2° lugar - 59.939 pts -
Clodoaldo Santos
3° lugar - 46.326 pts -
Buckminster
4° lugar - 26.573 pts -
Sidnei Serra
5° lugar - 26.171 pts -
Daniel Lara Souza
6° lugar - 18.258 pts -
Alberto Federman Neto.
7° lugar - 17.858 pts -
Mauricio Ferrari
8° lugar - 17.675 pts -
Diego Mendes Rodrigues
9° lugar - 15.808 pts -
edps
10° lugar - 15.305 pts
Scripts
A maior comunidade GNU/Linux da América Latina! Artigos, dicas, tutoriais, fórum, scripts e muito mais. Ideal para quem busca auto-ajuda.
Site hospedado por:
