Olá.
Seguindo minha apostila de java básico, fui fazer um exercício e me deparei com um conceito novo, a recursão. Um método chamando a ele mesmo.
Até onde cheguei, a apostila não mostra como fazer isso, lança o conceito como um desafio, num exercício.
Bom, eu consigo fazer algo que chegue no resultado esperado, mas não fazendo o método chamar a si mesmo. Gostaria que alguém resolvesse o desafio (que deve ser bem básico, uma vez que se conhece o recurso) pra que eu possa entender o conceito.
O texto do desafio é o seguinte:
[quote]Um método pode chamar ele mesmo. Chamamos isso de recursão. Você pode resolver a série de fibonacci
usando um método que chama ele mesmo. O objetivo é você criar uma classe, que possa ser usada da
seguinte maneira:
Fibonacci fibo = new Fibonacci();
int i = fibo.calculaFibonacci(6);
System.out.println(i);
Aqui imprimirá 8, já que este é o sexto número da série.
Este método calculaFibonacci não pode ter nenhum laço, só pode chamar ele mesmo como método. Pense
nele como uma função, que usa a própria função para calcular o resultado.[/quote]
Acho que o que eu fiz não é a solução esperada, mas uma utilização trivial de um método:
[code]class chamaFibo{
public static void main(String[] args){
Fibonacci fibo = new Fibonacci();
int i = fibo.calculaFibonacci(6);
System.out.println(i);
}
}
class Fibonacci{
int a=1;
int b=1;
int calculaFibonacci(int valor){
for(int i=1; i<valor; i+=1){
b=b+a;
a=b-a;
}
return a;
}
}[/code]
Tenho a impressão que a solução é algo do tipo x=f(x), mas não estou conseguindo colocar esse conceito em forma de código.
Hmmm… acho que entendi. Meu código ainda não está funcionando, mas acho que já está “recursivo”.
class Fibonacci{
int calculaFibonacci(int valor){
int a=0;
if (valor==0){
return 0;
}
if (valor== 1){
return 1;
}
for (int i=0; i<valor; i++){
Fibonacci fibo = new Fibonacci();
a += fibo.calculaFibonacci(i);
}
return a;
}
}Só me digam se estou no caminho certo. Ainda vou tentar consertar o código sozinho, pra chegar no valor certo.
Então, como diz no enunciado, a regra é não usar laço de repetição. O for que você usou no método calculaFibonacci é um laço de repetição. Isso quer dizer que você usou a abordagem iterativa.O exercício propõem que você use a abordagem recursiva. A abordagem recursiva tende a ser mais rápida que a abordagem iterativa, porem, custa mais memória uma vez que precisa guardar o estado de cada chamada recursiva anterior, principalmente se a linguagem nao tem um esquema de, digamos, cache para isso. Geralmente, se você sabe que não será usado um numero muito grande de chamadas recursivas, preferia recursividade senão laços de repetição. Geralmente na abordagem recursiva longos calculos geram estouro de memória.
[quote=Eliezer Reis]A abordagem recursiva tende a ser mais rápida que a abordagem iterativa, porem, custa mais memória uma vez que precisa guardar o estado de cada chamada recursiva anterior, principalmente se a linguagem nao tem um esquema de, digamos, cache para isso.[/quote]Ué! Olha só a próxima pergunta da apostila: [quote=apostila]Por que o modo acima é extremamente mais lento para calcular a série do que o modo iterativo (que se usa um laço)?[/quote]Eu achava que era por isso: ao invés de fazer uma conta atrás da outra, o computador ficava fazendo dúzias de contas, uma quantidade que crescia exponencialmente, dependendo do valor de entrada, armazenava tudo na memória e ainda tinha que somar os resultados. Agora fiquei boiando.
Quanto ao método, eu tinha esquecido o que era um "laço". Estou acostumado a chamá-los de "loops". Valeu pelo toque.
Me desculpem por não ter encontrado os tópicos sobre o assunto. Pesquisei por "recursão", mas parece que a ferramenta de busca não é muito boa. Usei ela pra pesquisar sobre operador condicional ternário e não achei nada. A primeira resposta da google apontava pra esse fórum!
Bom, antes de olhar os links, meu código ficou:class Fibonacci{
int calculaFibonacci(int valor){
//0 1 1 2 3 5 8 13...
//0 1 1+0 1+1 2+1 3+2 5+3 8+5...
if (valor==0){
return 0;
}
if (valor== 1){
return 1;
}
Fibonacci i = new Fibonacci();
int a = i.calculaFibonacci(valor-1);
Fibonacci j=new Fibonacci();
int b = j.calculaFibonacci(valor-2);
return (a+b);
}
}o que funcionou, mas ficou feio. Depois de olhar os links e pesquisar, melhorou:class Fibonacci{
int calculaFibonacci(int valor){
//0 1 1 2 3 5 8 13...
//0 1 1+0 1+1 2+1 3+2 5+3 8+5...
Fibonacci i = new Fibonacci();
return( (valor<=1) ? valor : i.calculaFibonacci(valor-1)+i.calculaFibonacci(valor-2));
}
}Então, quanto à recursão, minha dúvida já foi resolvida.
Já que a questão sobre a velocidade foi levantada aqui, gostaria de uma explicação a respeito: afinal, qual método é mais rápido?
Muito obrigado a todos! Inclusive ao DaniloM, que fez a pergunta que o dyeimys linkou.
[quote=ViniGodoy][quote=modesto76]se (n) valesse 6 não deveria retornar 9 ao invés de 8 por que: 6-1+6-2=9 ?
grato.[/quote]
Não. O cálculo realizado é calculaFibonacci(5) + calculaFibonacci(4) e não 5+4.[/quote] ViniGodoy, quando o programa chega nesta etapa, ela chama a recursão primeiro pra calculaFibonacci(n-1) ou calculaFibonacci(n-2). Qual chega ao caso base primeiro?
Ele chama na ordem que foi declarado. Ou seja, primeiro para calculaFibonacci(n-1).
Por exemplo, para fib(5) ele faz:
Chama calculaFibonacci de fib(4), ou seja n-1;
1.1. Por sua vez, isso chama calculaFibonacci(3), ou seja, n-1;
1.1.1. Por sua vez, isso chama calculaFibonacci(2), ou seja, n-1;
1.1.1.1 Por sua vez, isso chama calculaFibonacci(1), ou seja, n-1;
1.1.1.1.1. Isso retorna 1.
1.1.1.2. Chama então calculaFibonacci(0), ou seja, n-2;
1.1.1.2.1. Isso retorna 1.
1.1.1.3. Faz a soma de 1+1 e retorna o valor de calculaFibonacci(2).
1.1.2. Chama calculaFibonacci(1), ou seja, n-2;
1.1.2.1. Isso retorna 1.
1.1.3. Soma 2 + 1, o que dá 3 e retorna o valor de calculaFibonacci(3).
1.2. Chama calculaFibonacci(2), ou seja, n-2
1.2.1. Por sua vez, isso chama calculaFibonacci(1), ou seja, n-1;
1.2.1.1. Que retorna 1
1.2.2. E chama calculaFibonacci(0), ou seja, n-2
1.2.2.1. Que retorna 1
1.2.3. Faz a soma, que dá 2, ou seja, calculaFibonacci(2).
1.3. Faz a soma, ou seja, 3+2, obtendo assim calculaFibonacci(4).
Chama calculaFibonacci de fib(3), ou seja, n-2
2.1. Por sua vez, isso chama calculaFibonacci(2), ou seja, n-1;
2.1.1 Por sua vez, isso chama calculaFibonacci(1), ou seja, n-1;
2.1.1.1. Isso retorna 1.
2.1.2. Chama então calculaFibonacci(0), ou seja, n-2;
2.1.2.1. Isso retorna 1.
2.1.3. Faz a soma de 1+1 e retorna o valor de calculaFibonacci(2).
2.2. Chama calculaFibonacci(1), ou seja, n-2;
2.2.1. Isso retorna 1.
2.3. Soma 2 + 1, o que dá 3 e retorna o valor de calculaFibonacci(3).
Faz a soma de 3+5, e obtém calculaFibonacci(5), ou seja, 8.
