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.
Parte 2: 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.
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