Olá pessoal,
Como eu resolvo a série de Fibonacci( 0,1,1,2,3,5,8,13,21,34 ) utilizando um método recursivo, ja tentei inumeras vezes mas não consigo, esse negócio de orientação a objeto ta meio confuso na minha cabeça.
se alguém puder ajudar.
Salve,
veja o código:
public long fibonacci( long n ) {
if ( n == 0 || n == 1)
return 0;
else
return fibonacci( n - 1 ) + fibonacci( n - 2 );
}
, mas para resolver esse algoritmo você nem precisa usar orientação a objeto…!
só pra confundir um pouco mais…
em uma linha:
public long fibonacci( long n ) {
return (n == 0 || n == 1) ? 0 : (fibonacci( n - 1 ) + fibonacci( n - 2 ));
}
public long fibonacci( long n ) {
return (n == 0 || n == 1) ? 0 : (fibonacci( n - 1 ) + fibonacci( n - 2 ));
}
aproveitando o codigo acima, porfavor me iluminem:
depois do teste se n é igual a 0 ou 1 ele retorna 0, até aqui bleza!!
agora é que eu fico meio confuso- senao ele chama o proprio metodo fibonacci() dentro do proprio metodo??? 8O 8O 8O HELPPPPP!!!
agradeco qualquer ajuda!
[quote=“C3pO”]
public long fibonacci( long n ) {
return (n == 0 || n == 1) ? 0 : (fibonacci( n - 1 ) + fibonacci( n - 2 ));
}
aproveitando o codigo acima, porfavor me iluminem:
depois do teste se n é igual a 0 ou 1 ele retorna 0, até aqui bleza!!
agora é que eu fico meio confuso- senao ele chama o proprio metodo fibonacci() dentro do proprio metodo??? 8O 8O 8O HELPPPPP!!!
agradeco qualquer ajuda![/quote]
é meio complicado de entender, mas funciona assim:
se for 0 ou 1 ele retorna 0, caso contrario ele salva o contexto numa área de memória e chama o método novamente passando n-1, se n-1 for 0 ou 1 ele retorna o contexto anterior com o valor de retorno = 0, caso contrário ele salva um novo contexto e repete a chamada, e assim segue até que n seja 0 ou 1. É como se fosse sendo montada uma árvore de execução! Entendeu? é dificil entender pq nosso cérebro não funciona assim, mas o computador funciona.
o algoritmo tava errado, o certo é:public long fibonacci( long n ) {
return (n <= 0) ? 0 : ((n == 1) ? 1 : (fibonacci( n - 1 ) + fibonacci( n - 2 )));
}
vcs, são todos uns doidos…rs e eu tô ficando também.
valeu pessoal!!!
nossaaaaaaaaaaaaaaaaaaaaa
complicado hein???
mas assim,
em que momento vai aver a soma dos valores (10+9+8…)???
[quote=“C3pO”]nossaaaaaaaaaaaaaaaaaaaaa
complicado hein???
mas assim,
em que momento vai aver a soma dos valores (10+9+8…)???[/quote]
Nunca. É seqüência de Fibonacci. Os elementos só são somados numa série.
Esse problema não é bom pra ser resolvido com recursividade. Seria melhor usar um array, começando com 1 nos dois primeiros elementos. Daí, array[i] = array[i-1] + array[i-2]. Se quisesse somar tudo, bastaria percorrer o array, somando.
É só pra aprender recursividade mesmo. 
recursividade
me interesei pelo assunto
alguem sabe onde encontro algum material a respeito (se for em portugês melhor ainda)
desde de já um muito obrigado 
[quote=“Schuenemann”]
Nunca. É seqüência de Fibonacci. Os elementos só são somados numa série.
Esse problema não é bom pra ser resolvido com recursividade. Seria melhor usar um array, começando com 1 nos dois primeiros elementos. Daí, array[i] = array[i-1] + array[i-2]. Se quisesse somar tudo, bastaria percorrer o array, somando.
É só pra aprender recursividade mesmo. :)[/quote]
Os elementos são somados sim, afinal essa é a definição da sequência de fibonacci, “um elemento é igual a soma dos dois elementos anteriores”. Essa função recursiva é usa para saber o valor do enésimo elemento da sequência de fibonacci, ou seja, se vc chamar fibonacci(10) ele vai retornar o valor do 10º elemento da sequência (que é 55).
[quote=“C3pO”]nossaaaaaaaaaaaaaaaaaaaaa
complicado hein???
mas assim,
em que momento vai aver a soma dos valores (10+9+8…)???[/quote]
é dificil explicar só com palavras, ia ser mais fácil desenhar a execução do programa. Ele executa a soma quando houver o retorno da chamada recursiva da função, que só acontece quando o parâmetro chamado na função for 1 (nesse caso retorna 1 para a soma) ou quando for 0 (nesse caso retorna 0 para a soma).
Acho que isso é o máximo que eu consigo fazer com as palavras do meu vocabulário… hehehe
Ahh sim, claro. Entendi errado.
É que ele colocou no exemplo dele 10+9+8 (2 somas), e como falaram “série” no primeiro post, achei que se referia a somar todos os elementos.
C3p0, o exemplo mais fácil que conheço de se entender recursividade é a fatorial.
Seria mais ou menos assim: o método (ou função), pra resolver o problema, resolve chamar a si mesmo, só que passando uma versão mais simples do problema. E isso vai se repetir, até chegar no caso-base ou condição de parada.
Nessa página explica o exemplo do fatorial. Tá em php, mas simples de entender.
http://www.freecode.com.br/drartigos/artigo.php?cdart=207&id=17081
Sei que esse post é antigo, mas acredito que exista alguém com esse mesmo problema.
Cara, para definir uma função recursiva vc tem que entender muito bem o comportamento da função que vc está definindo, parece ser uma observação óbvia, mas é isso mesmo;
Você tem que verificar se dar para resolver o problema para uma dada entrada usando a resposta(ou seja a saida da função) para uma entrada menor do que a entrada em questão. Aí no caso, vc aplica a função(supondo que ela funciona para a entrada menor…isso mesmo, como se fosse uma coisa mágica hehe…e aí vc usa essa saída da entrada menor para responder a entrada maior. Eu recomendo fortemente vc tentar entender recursão de uma maneira teórica…sem ficar se preocupando com pilha de recursão…se você tiver alguma familiaridade com Demonstrações de Teoremas, Recursão é muito parecido com demonstrar teoremas por Indução Matemática.
O exemplo do fatorial:
fat(5) = 1x2x3x4x5
fat(4) = 1x2x3x4
observa que a saída do fat(5) é muito parecida com a saída do fat(4) …só muda pq a saída do fat(5), é igual a saída do fat(4) vezes 5, ou seja:
fat(5) = fat(4)*5
nesse caso nós supomos que a função fat funciona para 4 …e de posse desse resultado multiplicamos por 5…assim:
saidaAnterior = fat(4)
saidaTotal = saidaAnterior*5
Como a função sempre recorre a entradas menores para calcular a entrada…é preciso que isso tenha um fim…esse fim é o caso base, nesse caso:
fat(0) = 1.
Site recomendado: http://www.ime.usp.br/~pf/algoritmos/aulas/recu.html
Tente entender essa frase, se você conseguir entender…você conseguiu entender recursão:
“Para fazer um procedimento recursivo é preciso ter fé.” - prof. Siang Wun Song
Um abraço =)