recursão

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:

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.

Acho que o que eu fiz não é a solução esperada, mas uma utilização trivial de um método:

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.

Talvez ajude se você vir a definição matemática da série de Fibonacci:

Hmmm... acho que entendi. Meu código ainda não está funcionando, mas acho que já está "recursivo".
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.

A resolução do seu exercicio é bem a formulá que esta no link http://pt.wikipedia.org/wiki/Número_de_Fibonacci#Abordagem_recursiva

Na formula do link, quando houver o retorno de
if(n <2)
return n;

será desencadeado todas as somas pendentes das chamadas anteriores.

Esse outro link tem uma imagem que define como o um método é chamado na recursividade. http://pt.wikipedia.org/wiki/Recursividade_(ciência_da_computação)#Ordem_de_chamada_de_fun.C3.A7.C3.B5es

Melhorou ou piorou?

saim wrote:Só me digam se estou no caminho certo. Ainda vou tentar consertar o código sozinho, pra chegar no valor certo.

Ainda não, o caminho está errado. Não pode usar while, for ou outro laço de repetição.

Existe alguns tópicos aqui no GUJ tratando sobre isto!
Tem uma resposta do ViniGodoy excelente, vale apenas Conferir
http://www.guj.com.br/java/108080-fibonacci---calculo-recursivo

Eliezer Reis wrote: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.

Ué! Olha só a próxima pergunta da apostila:

apostila wrote:Por que o modo acima é extremamente mais lento para calcular a série do que o modo iterativo (que se usa um laço)?

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:o que funcionou, mas ficou feio. Depois de olhar os links e pesquisar, melhorou: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.

This message was edited 2 times. Last update was at 13/07/2011 08:25:02

Compare com a fórmula:

Fica ainda mais parecida se vc chamar a função calculaFibonacci de "f".

O mais estranho é que nossa ferramenta da busca é o próprio google.

JavaBaby Membro desde: 08/07/2011 21:03:00 Mensagens: 78 Offline

Acho que ainda não entendi!! ;P

Notícias, artigos e o maior fórum brasileiro sobre Java