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: 71.013 ]

Por: Jarno Trulli em 19/10/2004

1 0

Denuncie Favoritos Indicar Impressora

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:

Utilizando técnicas recursivas em C e C++

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

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

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    10

Rá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);
}

Agora vamos para dois programas mais "sérios".

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

BOCHS - O emulador de x86

GNU Emacs (Intro)

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

Leitura recomendada

Funcionamento da memória

Linguagem C - O primeiro programa

Liberando Memória ajustando o Tamanho das Strings em C

Estudo de ponteiros para GNU/Linux

Introdução a GTK+ 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

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